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

#define Nr_Noduri 1500
#define inf 2000000000
#define mod 104659
#define eps 0.000001

ifstream f("dmin.in");
ofstream g("dmin.out");
//ifstream f("dijkstra.in");
//ofstream g("dijkstra.out");
int Poz[Nr_Noduri],Fr[Nr_Noduri],Nr_drum[Nr_Noduri];
int end,n,m,i;
double Drum_min[Nr_Noduri];


struct heap{
	double val;
	int poz;
}Heap[Nr_Noduri];

struct nod{
	int varf;
	double dist;
};

vector<nod> L[Nr_Noduri]; 

inline void read(){
	
	nod nod2;
	int nod1,x;
	
	f>>n>>m;
	
	for(int i=1;i<=m;++i){
		f>>nod1>>nod2.varf>>x;
		nod2.dist=log(x);
		L[nod1].push_back(nod2);
	}
	
}

inline void initializare(){
	for(int i=1;i<=n;i++){
		Heap[++end].val=inf;
		Heap[end].poz=i;
		Poz[i]=i;
	}
	Heap[1].val=0;
	Nr_drum[1]=1;
}

inline int tata(int x){
	return x/2;
}

inline int left_son(int x){
	return 2*x;
}

inline int right_son(int x){
	return 2*x+1;
}	

inline void heap_down(int x){
	
	int aux2,sec;heap aux1;
	int l1,l2;
	while(x!=end){
		l1=left_son(x);
		l2=right_son(x);
		if(l1<=end&&l2<=end){
			if(Heap[l1].val<Heap[l2].val)
				sec=l1;
			else
				sec=l2;
		}
		else{
			if(l1<=end)
				sec=l1;
			else{
				if(l1<=end)
					sec=l2;
				else
					sec=x;
			}
		}
		if(Heap[sec].val>=Heap[x].val)
			break;
		
		aux2=Poz[Heap[sec].poz];
		Poz[Heap[sec].poz]=Poz[Heap[x].poz];
		Poz[Heap[x].poz]=aux2;
		aux1=Heap[sec];
		Heap[sec]=Heap[x];
		Heap[x]=aux1;
		x=sec;
		
	}
	
	
}

inline void heap_up(int x){
	heap aux1;int aux2,T;
	while(Heap[T=tata(x)].val>Heap[x].val&&x!=1){
		aux2=Poz[Heap[T].poz];
		Poz[Heap[T].poz]=Poz[Heap[x].poz];
		Poz[Heap[x].poz]=aux2;
		aux1=Heap[T];
		Heap[T]=Heap[x];
		Heap[x]=aux1;
		x=T;
	}
}

inline void update(int x){
	heap_up(x);
	heap_down(x);
}

inline int pop(){
	int nod1=Heap[1].poz;
	
	Drum_min[nod1]=Heap[1].val;
	
	Poz[Heap[end].poz]=1;
	
	Heap[1]=Heap[end--];
	
	update(1);
	
	return nod1;
}

inline void update_drum(int x){
	int poz;
	for(unsigned int i=0;i<L[x].size();i++){
		poz=Poz[L[x][i].varf];
		if(Heap[poz].val>Drum_min[x]+L[x][i].dist+eps&&Fr[L[x][i].varf]==0){
			Heap[poz].val=Drum_min[x]+L[x][i].dist;
			Nr_drum[L[x][i].varf]=Nr_drum[x];
			update(poz);
		}
		else if(Drum_min[x]+L[x][i].dist-Heap[poz].val<=eps){
			Nr_drum[L[x][i].varf]+=Nr_drum[x];
			if(Nr_drum[L[x][i].varf]>=mod)
				Nr_drum[L[x][i].varf]-=mod;
		}
	}
	
}

inline void dijkstra(){
	
	int x;
	
	while(end!=0){
		x=pop();
		Fr[x]=1;
		update_drum(x);
	}
	
}

int main(){
	
	read();
	
	initializare();
	
	dijkstra();
	
	for(i=2;i<=n;i++)
		g<<Nr_drum[i]<<" ";

	f.close();
	g.close();
	
	return 0;
}