#include<fstream>
#include<vector>
#include<cstring>
#include<utility>

#define NN 1509
#define nn  104659
#define INF 0x3f3f3f3f
#define mp make_pair
#define f first
#define s second
#define pb push_back

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

vector<vector<pair <long long ,long long > > >G;
int n,m,v[NN];
long long d[NN],f[NN];
void read();
void dijkstra(int);
void write();

int main()
{
	read();
	dijkstra(1);
	write();
	return 0;
}

void read()
{
	ifstream in("dmin.in");
	in>>n>>m;
	int i,j,c;
	G.resize(n+1);
	for(;m;--m)
	{
		in>>i>>j>>c;
		G[i].pb(mp(j,c));
		G[j].pb(mp(i,c));
	}
}

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

void dijkstra(int start)
{
	int i,j,k,poz;
	memset(d,INF,sizeof(d));
	for(i=0;i<G[start].size();++i)
	{
		d[G[start][i].f]=G[start][i].s;
		(f[G[start][i].f]++)%nn;
	}
	v[start]=1;
		for(int i=1;i<n;i++)
		{
			int minim=INF;
				for(int j=1;j<=n;j++)
					if(d[j]<minim&&!v[j])
						{
							minim=d[j];
							poz=j;
					}
					v[poz]=1;
						for(k=0;k<G[poz].size();++k)
							if(d[G[poz][k].f]>d[poz]*G[poz][k].s)
								{
									d[G[poz][k].f]=d[poz]*G[poz][k].s;
									f[G[poz][k].f]=f[poz]%nn;
								}
							else
								if(d[G[poz][k].f]==d[poz]*G[poz][k].s)
									f[G[poz][k].f]+=f[poz]%nn;
		}
		
}