#include<fstream>
#include<vector>
#include<queue>
#define dmax 1505
#define mult 1000000000
using namespace std;
ifstream in("dmin.in");
ofstream out("dmin.out");

long long n,m,nrd[dmax];
long long dm[dmax];
bool t[dmax];

struct muchie
{	int v;
	long long c;
};

vector<struct muchie>g[dmax];
vector<struct muchie>::iterator it;
queue<int>q;

void bellman()
{	long long i,crt;
	for(i=1;i<=n;i++)
		dm[i]=mult;
	q.push(1);
	t[1]=1;
	dm[1]=0;
	nrd[1]=1;
	while(!q.empty() )
	{	crt=q.front();
		q.pop();
		t[crt]=0;
		for(it=g[crt].begin();it < g[crt].end();it++)
		{	if(dm[crt] + it->c < dm[it->v])
			{	dm[it->v]=dm[crt]+it->c;
				nrd[it->v]=nrd[crt];
				if(nrd[it->v] > 104659)
					nrd[it->v]%=104659;
				if(!t[it->v])
				{	q.push(it->v);
					t[it->v]=1;
				}
			}	
			else if(dm[crt] + it->c == dm[it->v])
			{	nrd[it->v]+=nrd[crt];	
				if(nrd[it->v] > 104659)
					nrd[it->v]%=104659;
			}	
		}
	}	
	for(i=2;i<=n;i++)
		out<<nrd[i]<<" ";
}	
int main()
{	long long i,a,b,r;
	muchie w;
	in>>n>>m;
	for(i=1;i<=m;i++)
	{	in>>a>>b>>r;	
		w.c=r;
		w.v=b;
		g[a].push_back(w);
		w.v=a;
		g[b].push_back(w);
	}
	in.close();
	bellman();
	out.close();
	return 0;
}