#include <iostream>
#include <fstream>
#include <vector>
#include <cmath>
#include <iomanip>
#include <set>

using namespace std;

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

const int mo = 104659;
const double INF = 0x3f3f3f3f3f3f3f3f;

struct muc{
	int a, b;
	double v;
	int ott(int x){
		if(x == a){
			return b;
		}else{
			return a;
		}
	}
};

struct nod{
	int a;
	double v;
	bool operator<(const nod &rhs)const{
		return v < rhs.v;
	}
};

int n, m;
vector<muc> wu;
vector<int> gra[1541];

double dis[1541];
int sol[1541];
set<nod> qu;
bool vi[1541];

void nuke(){
	for(int i = 2; i <= n; ++i){
		dis[i] = INF;
	}
	sol[1] = 1;
	qu.insert({1, 0});
}

bool apx(double a, double b){
	return abs(a-b)<=0.000000001;
}

void dik(){
	nuke();
	while(!qu.empty()){
		nod no = *qu.begin();qu.erase(qu.begin());
		int a = no.a;
		vi[a] = true;
		for(auto mi : gra[a]){
			muc mu = wu[mi];
			int b = mu.ott(a);
			if(!vi[b]){
				double v = dis[a]+mu.v;
				if(v < dis[b]){
					if(!apx(dis[b], INF)){
						qu.erase({b, dis[b]});
					}
					dis[b] = v;
					qu.insert({b, dis[b]});
					sol[b] = sol[a];
				}else if(apx(v, dis[b])){
					sol[b] += sol[a];
				}
				sol[b] %= mo;
			}
		}
	}
}

int main(){
	fin >> n >> m;
	for(int i = 0; i < m; ++i){
		muc x;
		fin >> x.a >> x.b >> x.v;
		x.v = log2(x.v);
		
		wu.push_back(x);
		gra[x.a].push_back(i);
		gra[x.b].push_back(i);
	}
	dik();
	for(int i = 2; i <= n; ++i){
		fout << sol[i] << " ";
	}
	return 0;
}