#include<fstream>
#include<vector>
#include<bitset>
#include<queue>
#include<cmath>
#define MOD 104659
#define eps 1e-9
using namespace std;ifstream is("dmin.in");ofstream os("dmin.out");double D[1505];int N,M,Nr[1505];bitset<1505>B;vector<pair<int,double>>v[1505];struct CMP{bool operator()(int a,int b){return D[a]>D[b];}};priority_queue<int,vector<int>,CMP>Q;main(){is>>N>>M;for(int i=2;i<=N;++i)D[i]=(1<<30);double cost;for(int i=1,a,b,c;i<=M;++i){is>>a>>b>>c;cost=log(c);v[a].push_back({b,cost});v[b].push_back({a,cost});}Q.push(1);Nr[1]=1;for(int i,nod;!Q.empty();){i=Q.top();Q.pop();if(B[i])continue;B[i]=1;for(int j=0;j<v[i].size();++j){nod=v[i][j].first;cost=v[i][j].second;if(fabs(D[nod]-D[i]-cost)<eps)Nr[nod]=(Nr[nod]+Nr[i])%MOD;else if(D[nod]>D[i]+cost){Nr[nod]=Nr[i];D[nod]=D[i]+cost;Q.push(nod);}}}for(int i=2;i<=N;++i)os<<Nr[i]<<' ';is.close();os.close();}