#include<fstream>
#include<vector>
#include<math.h>
#define NMAX 1502
#define inf 40000000
#define eg 0.00000001
using namespace std;
int D[NMAX],n,m,i,j,a,b,nr[NMAX],H[NMAX],N,poz[NMAX],nod,minu;
ifstream f("dmin.in");
ofstream g("dmin.out");
vector< pair <int,int> >G[NMAX];
int rs(int k){
	return 2*k+1;
}
int ls(int k){
	return 2*k;
}
void sift(int k){
	int son=k;
	if(ls(k)<=N && D[H[ls(k)]] <D[H[son]])
		son=ls(k);
	if(rs(k)<=N && D[H[rs(k)]]  <D[H[son]])
		son=rs(k);
	if(son!=k)
		sift(son);
}
void percolate(int k){
	while(k>1 && D[H[k]]<D[H[k/2]]){
		swap(poz[H[k]],poz[H[k/2]]);
		swap(H[k],H[k/2]);
		k/=2;
	}
}
void insert(int x){
	H[++N]=x;
	poz[x]=N;
	percolate(poz[x]);
}
void getmin(){
	minu=H[1];
	swap(poz[H[1]],poz[H[N]]);
	swap(H[1],H[N]);
	--N;
	sift(poz[1]);

}
void init(){
	for(i=1;i<=n;i++){
		if(i!=a)
			D[i]=inf;
	}
	D[a]=0;
}
void dijkstra(){
	insert(a);
	for(;N;){
		getmin();
		nod=minu;
		for(int i=0;i<G[nod].size();++i){
			if( D[G[nod][i].first]==D[nod]+G[nod][i].second){
				nr[G[nod][i].first]+=nr[nod];
				if(nr[G[nod][i].first]>=104569)
					nr[G[nod][i].first]-=104569;
			}
			else{
				if(D[G[nod][i].first]>D[nod]+G[nod][i].second){
					D[G[nod][i].first]=G[nod][i].second+D[nod];
					if(poz[G[nod][i].first])
						percolate(poz[G[nod][i].first]);
					else
						insert(G[nod][i].first);
					nr[G[nod][i].first]=nr[nod];
				}
			}
		}
	}
}
int main (){
	f>>n>>m;
	int w,e,r;
	for(i=1;i<=m;i++){
		f>>w>>e>>r;
		G[w].push_back(make_pair(e,r));
		G[e].push_back(make_pair(w,r));
	}
	a=1;
	nr[a]=1;
	init();
	dijkstra();
	for(i=1;i<=n;i++){
		if(i!=a)
			g<<nr[i]<<" ";
	}
	return 0;
}