#include <iostream>
#include <fstream>
#include <algorithm>
#include <cmath>
#include <vector>
#include <queue>

using namespace std;

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

typedef long double doubly;

const doubly INF = 100000;
const int MODIT = 104659;

bool eq(doubly lhs, doubly rhs){
	return abs(lhs-rhs) <= 0.000000001;
}

struct edg{
	int b;doubly d;
};
struct nod{
	int a;doubly d;
	bool operator<(const nod &rhs)const{
		if(d != rhs.d){
			return d > rhs.d;
		}else{
			return a > rhs.a;
		}
	}
};

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

doubly dst[1541];
int pth[1541];
priority_queue<nod> pq;

int main(){
	// ios_base::sync_with_stdio(false);
	
	fin >> n >> m;
	for(int i = 0; i < m; ++i){
		int a, b;doubly fd;
		fin >> a >> b >> fd;
		
		doubly d = log2(fd);
		gra[a].push_back({b,d});
		gra[b].push_back({a,d});
	}
	
	for(int i = 2; i <= n; ++i)dst[i] = INF;
	
	pth[1] = 1;
	pq.push({1,0});
	while(!pq.empty()){
		auto nd = pq.top();pq.pop();
		int a = nd.a;
		if(nd.d > dst[a])continue;
		
		for(auto ed : gra[a]){
			int b = ed.b;
			doubly d = ed.d;
			if(dst[a]+d < dst[b]){
				dst[b] = dst[a]+d;
				pq.push({b,dst[b]});
				
				pth[b] = pth[a];
			}else if(eq(dst[a]+d, dst[b])){
				pth[b] += pth[a];
				pth[b] %= MODIT;
			}
		}
	}
	
	for(int i = 2; i <= n; ++i){
		fout << pth[i] << " ";
	}
	
	return 0;
}