#include<bits/stdc++.h>
#define ll long long
#define PII pair<ll,ll>
using namespace std;
ll t,d[1000005],ans[1000006];
ll n,m,fl,x,y,z;
bool f[1000005];
struct ed
{
	ll nx;
	ll dnl;
	ll num;
}a[2000005];
ll hd[2000005],idz;
void in_ed(ll in,ll on,ll nu)
{
	idz++;
	a[idz].nx=hd[in];
	a[idz].dnl=on;
	a[idz].num=nu;
	hd[in]=idz;
}
void dijkstra(ll s)
{
	memset(f,0,sizeof(f));
    memset(d,0x3f3f3f3f,sizeof(d));
    d[s]=0;
    ans[s]=1;
    priority_queue<PII,vector<PII>,greater<PII> >heap;
    heap.push({0,1});
    while(heap.size())
    {
        PII k=heap.top();
        heap.pop();
        ll ver=k.second;
        ll distance=k.first;
        if(f[ver])continue;
        f[ver]=1;
        for(ll i=hd[ver];i!=0;i=a[i].nx)
        {
            ll j=a[i].dnl;
            if(d[j]==distance+a[i].num)
            {
            	ans[j]+=(ans[ver]%100003);
                ans[j]%=100003;
            }
            if(d[j]>distance+a[i].num)
            {
                d[j]=distance+a[i].num;
                ans[j]=ans[ver]%100003;
				heap.push({d[j],j});
			}
		}
	}
}
int main()
{
	freopen("P1144_6.in","r",stdin);
	freopen("P1144_6.txt","w",stdout);
	cin>>n>>m;
	for(ll i=1;i<=n;i++)
	{
		d[i]=INT_MAX;
	}
	for(ll i=1;i<=m;i++)
	{
		scanf("%lld%lld",&x,&y);
		z=1;
		in_ed(x,y,z);
		in_ed(y,x,z);
	}
	dijkstra(1);
	for(ll i=1;i<=n;i++)
	{
		printf("%lld\n",ans[i]);
	}
    return 0;
}

求教!!!