//Vasilut
#include<fstream>
#include<cstdio>
#include<vector>
#include<queue>
#include<bitset>
#include<cmath>
#include<utility>

using namespace std;
ofstream out("dmin.out");

#define NN 1510
#define INF 0x3f3f3f3f
#define MOD 104659
#define mp make_pair
#define pb push_back
#define f first
#define s second 
#define INFF(x) memset(x,INF,sizeof(x))

vector<pair<int ,double > > G[NN];
typedef vector<pair<int,double> > ::iterator IT;
queue<int>Q;
bitset<NN>uz;

int drum[NN],n,m;
double d[NN],EPS=0.0000000001,c;

void read();
void BMF();
void write();

int main()
{
	read();
	BMF();
	write();
	return 0;
}

void read()
{
	ifstream in("dmin.in");
	in>>n>>m;
	for(int x,y,c ; m ; --m)
	{
		in>>x>>y>>c;
		G[x].pb(mp(y,log( (double) c) ) );
		G[y].pb(mp(x,log( (double) c) ) );
	}
}

void BMF()
{
	for(int i=1;i<=n;i++)
		d[i]=INF;
	d[1]=0;
	drum[1]=1;
	Q.push(1);
	uz[1]=1;
	int k;
	for(; Q.size(); Q.pop())
	{
			k=Q.front();
				for(IT I=G[k].begin();I!=G[k].end();++I)
				{
					int val=I->f;
					double cost=I->s;
					if( fabs( d[val] - d[k] - cost ) < EPS )
						drum[val]+= (drum[k] ) %MOD;
					else
						if( d[val] - d[k] - cost > EPS)
						{
							if(!uz[val])
							{
								Q.push(val);
								uz[val]=1;
							}
							d[val]=d[k] + cost;
							drum[val]= drum[k] ;
						}
				}
				uz[k]=0;
	}
}

void write()
{
	for(int i=2;i<=n;i++)
		out<<drum[i]<<" ";
}