#include<bits/stdc++.h>
#define ll long long
#define inf 0x3f3f3f3f
#define PII pair<int, int>
using namespace std;

struct point{
	ll to, next;
}edge[4000010];
ll n, m, head[4000010], ans[4000010], dis[4000010];
bool vis[4000010];
void dijkstra(){
	priority_queue<PII, vector<PII>, greater<PII>>q;
	for(ll i=1; i<=n; i++)
		dis[i]=inf;
	q.push({1, 1});
	ans[1]=1;
	dis[1]=0;
	while(!q.empty()){
		auto t=q.top();
		q.pop();
		ll num=t.second, distant=t.first;
		if(vis[num])
			continue ;
		vis[num]=true;
		for(ll k=head[num]; k!=-1; k=edge[k].next){
			if(dis[edge[k].to]>dis[num]+distant){
				dis[edge[k].to]=dis[num]+distant;
				ans[edge[k].to]=0;
				q.push({dis[edge[k].to], edge[k].to});
			}
			if(dis[edge[k].to]==dis[num]+distant){
				ans[edge[k].to]+=ans[num];
				ans[edge[k].to]%=100003;
			}
		}
	}
	return ;
}
int main(){
	scanf("%lld %lld", &n, &m);
	for(ll i=1; i<=n; i++)
		head[i]=-1;
	ll u, v;
	for(ll i=1; i<=2*m; i++){
		scanf("%lld %lld", &u, &v);
		edge[i].to=v, edge[i].next=head[u];
		head[u]=i;
		i++;
		edge[i].to=u, edge[i].next=head[v];
		head[v]=i;
	}
	dijkstra();
	for(ll i=1; i<=n; i++)
		printf("%lld\n", ans[i]);
	return 0;
}