直接用佛洛依德会溢出，实际上最先输入的边即最短距离，用并查集

#include <iostream>
#include <vector>
#include <climits>
using namespace std;
vector<int> parents;
int find(int x) {
    return x == parents[x] ? x : parents[x] = find(parents[x]);
}
int main() {
    int n, m;
    cin >> n >> m;
    parents.resize(n);
    for (int i = 0; i < n; i++) parents[i] = i;
    vector<vector<int>> grid(n, vector<int>(n, INT_MAX));
    for (int i = 0, len = 1; i < m; i++, len = len * 2 % 100000) {
        int a, b;
        cin >> a >> b;
        if (find(a) != find(b)) {
            parents[find(a)] = find(b);
            grid[a][b] = grid[b][a] = len;
        }
    }
    for (int k = 0; k < n; k++) {
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                if (grid[i][k] != INT_MAX && grid[k][j] != INT_MAX &&grid[i][k] + grid[k][j] < grid[i][j]) grid[i][j] =grid[i][k] +grid[k][j];
            }
        }
    }
    for (int i = 1; i < n; i++) {
        if (grid[0][i] == INT_MAX) cout << -1 << endl;
        else cout << grid[0][i] % 100000 << endl;
    }
    return 0;
}