#include<cstdio>
#include<vector>
#include<queue>
#include<cmath>
#define NMAX 1505
#define INF (1<<30)
#define DIJKSTRA_TYPE pair<double,short> 
#define MOD 104659
#define PREC 0.000001
using namespace std;
FILE *fin,*fout;
vector < pair<short,double> > G[NMAX];
int n,k,apar[NMAX];
double d[NMAX];
priority_queue< DIJKSTRA_TYPE, vector<DIJKSTRA_TYPE>, greater<DIJKSTRA_TYPE> > HEAP;
bool use[NMAX];
void dijkstra(short nod)
{
short vec;
double cost;
for(int i=1;i<=n;i++)
d[i]=INF;
d[nod]=0;
apar[1]=1;
HEAP.push(make_pair(0,nod));
while(!HEAP.empty())
{
nod=HEAP.top().second;
HEAP.pop();
if(use[nod])
continue;
use[nod]=1;
for(size_t i=0;i<G[nod].size();i++)
{
vec=G[nod][i].first;
cost=G[nod][i].second;
if(use[vec])
continue;
if(d[vec]>d[nod]+cost+PREC)
{
d[vec]=d[nod]+cost;
apar[vec]=apar[nod];
HEAP.push(make_pair(d[vec],vec));
continue;
}
if(abs(d[vec]-d[nod]-cost)<=PREC)
{
apar[vec]+=apar[nod];
apar[vec]%=MOD;
}
}
}
}
void read()
{
fin=fopen("dmin.in","r");
int x,y,m;
double z;
fscanf(fin,"%d %d",&n,&m);
while(m--)
{
fscanf(fin,"%d %d %lf",&x,&y,&z);
z=log(z);
G[x].push_back(make_pair(y,z));
G[y].push_back(make_pair(x,z));
}
fclose(fin);
}
void print()
{
fout=fopen("dmin.out","w");
for(int i=2;i<=n;i++)
fprintf(fout,"%d ",apar[i]);
fclose(fout);
}
int main()
{
read();
dijkstra(1);
print();
return 0;
}