#include<cstdio>
#include<vector>
#include<algorithm>
#include<cstring>
#include<deque>
#define MAX 1505
#define mod 104659
using namespace std;
int n,i,j,k,m;
long long x,y,a,b,cost[MAX];
int rez[MAX];
vector<pair<int,int> >v[MAX];
bool viz[MAX];
deque<int>c;
struct nod
{
    int poz;
    long long cos;
}s[MAX];
 
void dijkstra(int x)
{
    c.push_back(x);
    viz[x]=true;
    while (!c.empty())
    {
        x=c.front();
        for (j=0;j<v[x].size();j++) 
        {
            a=v[x][j].first;
            b=v[x][j].second;
            if (!viz[a]) cost[a]=cost[x]+b,viz[a]=true,c.push_back(a);else
                 if (cost[a]>cost[x]+b) cost[a]=cost[x]+b,c.push_back(a);
        }
        c.pop_front();
    }
}
long long cmp(const nod x,const nod y)
{
    return x.cos<y.cos;
}
 
int main()
{
    freopen("dmin.in","r",stdin);
    freopen("dmin.out","w",stdout);
    scanf("%d %d",&n,&m);
    for (i=1;i<=m;i++) scanf("%d %d %lld",&a,&b,&k),v[a].push_back(make_pair(b,k)),v[b].push_back(make_pair(a,k));
    dijkstra(1);
    for (i=2;i<=n;i++) s[i].poz=i,s[i].cos=cost[i];
    sort(s+1+2,s+n+1,cmp);
    c.push_back(1);
    memset(viz,false,sizeof(viz));
    s[1].poz=1;
    rez[1]=1;viz[1]=true;
	for (i=1;i<=n;i++)
	{
		x=s[i].poz;
		for (j=0;j<v[x].size();j++)
		{
			a=v[x][j].first;
			b=v[x][j].second;
			if (cost[a]==cost[x]+b) rez[a]=(rez[a]+rez[x])%mod;
			viz[a]=true;
		}
	}
    for (j=2;j<=n;j++) printf("%d ",rez[j]);
    return 0;
}