#include<stdio.h>
#include<math.h>
#include<vector>
#include<queue>
using namespace std;

#define fs first
#define sc second
#define pb push_back
#define eps 1e-9
#define R 104659
#define INF 1000000

typedef pair<double, int> di;
vector <di> nr[1510];
priority_queue <di, vector<di>, greater<di> > Q;
int sol[1510];
double dist[1510];
int n,m;
inline double modul(double aa){
	if(aa<0)
		return -aa;
	return aa;
}
void solve(){
	int i,ss,x,y;
	double dy;
	vector <bool> viz(1510,false);
	while(!Q.empty()){
		x=Q.top().sc;
		Q.pop();
		if(viz[x])
			continue;
		viz[x]=true;
		ss=int(nr[x].size());
		for(i=0;i<ss;++i){
			y=nr[x][i].sc;
			dy=nr[x][i].fs;
			if(modul(dist[x]+dy-dist[y])<eps){
				sol[y]+=sol[x];
				if(sol[y]>=R)
					sol[y]-=R;
			}
			else{
				if(dist[x]+dy<dist[y]){
					dist[y]=dist[x]+dy;
					sol[y]=sol[x];
					Q.push(di(dist[y],y));
				}
			}
		}
	}
}
int main(){
	freopen("dmin.in","r",stdin);
	freopen("dmin.out","w",stdout);
	int i,a,b,c;
	double cc;
	scanf("%d%d",&n,&m);
	for(i=0;i<m;++i){
		scanf("%d%d%d",&a,&b,&c);
		cc=double(log2(c));
		nr[a].pb(di(cc,b));
		nr[b].pb(di(cc,a));
	}
	Q.push(di(0,1));
	for(i=2;i<=n;++i)
		dist[i]=INF;
	sol[1]=1;
	solve();
	
	for(i=2;i<=n;++i)
		printf("%d ",sol[i]);
	printf("\n");
	
	fclose(stdin);
	fclose(stdout);
	return 0;
}