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

struct point{
	ll to, next;
}edge[4000010];
ll n, m, head[4000010], ans[4000010], dis[4000010], ii;
bool vis[4000010];
void add(ll v, ll u){
	edge[ii].to=v, edge[ii].next=head[u];
	head[u]=ii;
	ii++;
	return ;
}
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]=ans[num];
				q.push({dis[edge[k].to], edge[k].to});
			}
			else 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<=m; i++){
		scanf("%lld %lld", &u, &v);
		add(u, v);
		add(v, u);
	}
	dijkstra();
	for(ll i=1; i<=n; i++)
		printf("%lld\n", ans[i]%100003);
	return 0;
}