#include <fstream>
#include <queue>
#include <cmath>

using namespace std;
vector< pair<double, int> > v[1505];
priority_queue< pair<double, int> > q;
double best[1505];
int f[1505];
int main()
{
	ifstream cin("dmin.in");
	ofstream cout("dmin.out");

    int n,m,a,b,c;
    pair<double, int> pa,ca;
    cin>>n>>m;
    for(int i=1;i<=n;i++)
	{
		best[i]=-2100000000;
	}

    while(cin>>a>>b>>c)
	{
		pa.second=b;
		pa.first=(log2(c))*(-1);
		v[a].push_back(pa);
		pa.second=a;
		v[b].push_back(pa);
	}

	pa.first=0;
	pa.second=1;
	best[1]=0;
	f[1]=1;
	q.push(pa);
	while(!q.empty())
	{
		pa=q.top();
		q.pop();
		if(pa.first==best[pa.second])
		{
			for(int i=0;i<v[pa.second].size();i++)
			{
				ca.second=v[pa.second][i].second;
				ca.first=v[pa.second][i].first+pa.first;
				if(ca.first>best[ca.second])
				{
					best[ca.second]=ca.first;
					f[ca.second]=f[pa.second]%104659;
					f[ca.second]%=104659;
					q.push(ca);
				}
				else if(ca.first==best[ca.second])
				{
					f[ca.second]+=f[pa.second]%104659;
					f[ca.second]%=104659;
				}
			}

		}
	}

	for(int i=2;i<=n;i++)
	{
		if(best[i]==-2100000000)
		{
			best[i]=0;
			f[i]=0;
		}
		cout<<f[i]<<" ";
	}

    return 0;
}