用dijk堆优化做的，检查半天发现调用完dijk()还必须要将cnt[1]第二次赋值成1才可以，不理解为什么出现这种情况。#include<bits/stdc++.h>
using namespace std;
const int N = 1000010;
const int MOD = 100003;
int h[N], ne[N], e[N], idx=0, dist[N], cnt[N];
bool st[N];
typedef pair<int, int>PII;
void add(int a, int b) {
	e[idx] = b;
	ne[idx] = h[a];
	h[a] = idx++;
}
void dijk() {
	priority_queue<PII, vector<PII>, greater<PII>>heap;
memset(dist,0x3f,sizeof dist);

	heap.push({0, 1});
	cnt[1] = 1;
	while (heap.size()) {
		auto t = heap.top();

		heap.pop();

		int distance = t.first, u = t.second;
		if (st[u])continue;
		st[u] = true;
		for (int i = h[u]; i != -1; i = ne[i]) {

			int j = e[i];
			if (dist[j] > distance + 1) {
				dist[j] = distance + 1;
				cnt[j] = cnt[u];
			heap.push({dist[j], j});
			
			} else if (dist[j] == distance + 1) {
			cnt[j]=(cnt[j]+cnt[u])%MOD;
			
			}

		}
	}

}

int main() {
    memset(h,-1,sizeof h);
	int n, m;
	cin >> n >> m;
	while (m--) {
		int a, b;
		cin >> a >> b;
		add(a, b);
		add(b, a);
	}
	dijk();
	int ans = 0;
	cnt[1]=1;//！！！不清楚的地方！！！
	for (int i = 1; i <= n; i++) {
cout<<cnt[i]<<endl;
	}

}