好题！并查集生成Kruskal+队列优化Dijkstra
Prim和Dijkstra除点权更新方式不同以外，其余遍历方式均相同，所以练了本题等于同时练了Prim和Kruskal~
Prim生成后的两点之间的路径是唯一的（若不唯一，则可以绕起点和终点成圈，说明我们生成的图不是最小生成树）。
 因此，我们不必在意边权具体是多少，只要让最短路径经过的点数最小即可。 
又：路径经过的点数最小等同于经过边数最小， 在代码实现中，由于边权均小于MOD，且MOD*MAXN<INT_MAX一定成立，
因此我们可以用在初始化中已经对MOD取过模的边权之和最小代替经过边数最小，作为Dijkstra状态更新的依据~
代码如下：
#include<cstdio>
#include<vector>
#include<queue>
#include<algorithm>

#define MOD 100000
#define MAXN 100
#define MAX 1e9
struct node{
    int weight;
    int nodeIdx;
    node(int w, int i):weight(w), nodeIdx(i){}
};
struct cmp{
    bool operator()(node a, node b){
        return a.weight>b.weight;
    }
};
std::priority_queue<node, std::vector<node>, cmp> queue;
std::vector<node> edges[MAXN];
int father[MAXN];
int dis[MAXN];
int find(int x){
    while(father[x]!=x){
        x=father[x];
    }
    return x;
}
bool merge(int x, int y){
    int fx = find(x);
    int fy = find(y);
    if(fx!=fy){
        father[fx]=fy;
    }
    return fx!=fy;
}
int main(){
    int n, m;
    scanf("%d%d",&n,&m);
    for(int i=0;i<n;++i){
        father[i]=i;
        dis[i]=MAX;
    }
    dis[0]=0;
    for(int i=0, len=1;i<m;++i,len=(2*len)%MOD){
        int u, v;
        scanf("%d%d",&u,&v);
        if(merge(u,v)){
            edges[v].push_back(node(len, u));
            edges[u].push_back(node(len, v));
        }
    }
    std::fill(dis, dis+n, MAX);
    dis[0] = 0;
    queue.push(node(0, 0));
    while(!queue.empty()){
        auto nd = queue.top();
        queue.pop();
        int from = nd.nodeIdx;
        if(nd.weight>dis[from]) continue;
        for(auto edge: edges[from]){
            int to = edge.nodeIdx;
            int w = edge.weight;
            if(dis[to]>dis[from]+w){
                dis[to] = dis[from]+w;
                queue.push(node(dis[to], to));
            }
        }
    }
    for(int i=1;i<n;++i){
        if(dis[i]==MAX){
            printf("-1\n");
        }else{
            printf("%d\n", dis[i]%MOD);
        }
    }
    return 0;
}