#include <fstream>
#include <vector>
#include <set>
#define DIM 104659
#define INF 99999999
using namespace std;
ifstream f("dmin.in");
ofstream g("dmin.out");
int n,m,D[1511],R[1511];
bool viz[1511];

vector<pair<long long,int> > L[1511];
set<pair<long long,int> > S;

int main(void){
	register int i,j,c,x,y,nod;
	register long long val;
	pair<long long,int> q,p;
	
	f>>n>>m;
	for(i=1;i<=m;i++){
		f>>x>>y>>c;
		L[x].push_back(make_pair(c,y));
		L[y].push_back(make_pair(c,x));
	}
	for(i=2;i<=n;i++)
		D[i]=INF;
	D[1]=1;
	R[1]=1;
	
	S.insert(make_pair(1,1));
	while(!S.empty()){
		val=S.begin()->first;
        nod=S.begin()->second;
		S.erase(S.begin());
		if(viz[nod])
			continue;
		for(i=0;i<L[nod].size();i++){
			q=L[nod][i];
			if(!viz[q.second]){
				val=(D[nod]*q.first)%DIM;
				if(D[q.second]>val){
					D[q.second]=val;
					S.insert(make_pair(D[q.second],q.second));
					R[q.second]=R[nod];
				}
				else if(D[q.second]==val)
					R[q.second]+=R[nod];
			}
		}
		viz[nod]=true;
	}
	
	for(i=2;i<=n;i++)
		g<<R[i]<<" ";
	return 0;
}