#include <bits/stdc++.h>
#define NMAX 1505
#define MOD 104659
#define INF 0x3f3f3f3f
#define cst first
#define nod second

using namespace std;

ifstream fin("dmin.in");
ofstream fout("dmin.out");

vector < pair<double,int> > mv[NMAX];
priority_queue < pair<double,int>, vector< pair<double,int> >, greater< pair<double,int> > > q;
double cost[NMAX];
int viz[NMAX];
int answer[NMAX];

void dijkstra(int s){
	int i,x;

	cost[s]=0;
	answer[s]=1;
	q.push(make_pair(0.0,s));

	while(!q.empty()){
		x=q.top().nod;
		q.pop();

		if(viz[x])
			continue;

		viz[x]=1;

		for(i=0;i<mv[x].size();i++){
			if(cost[mv[x][i].nod]>cost[x]+mv[x][i].cst){
				cost[mv[x][i].nod]=cost[x]+mv[x][i].cst;
				answer[mv[x][i].nod]=answer[x];
				q.push(make_pair(cost[mv[x][i].nod],mv[x][i].nod));
			}
			else if(cost[mv[x][i].nod]==cost[x]+mv[x][i].cst){
				answer[mv[x][i].nod]+=answer[x];
				answer[mv[x][i].nod]%=MOD;
			}
		}
	}
}

int main(){
	int n,m,x,y,c,c1,i;

	fin>>n>>m;

	for(i=1;i<=n;i++)
		cost[i]=INF;

	for(i=1;i<=m;i++){
		fin>>x>>y>>c;

		c1=log2(1.0*c);

		mv[x].push_back(make_pair(c,y));
		mv[y].push_back(make_pair(c,x));
	}

	dijkstra(1);

	for(i=2;i<=n;i++)
		fout<<answer[i]<<" ";

    return 0;
}