#include <bits/stdc++.h>
#include <queue>
using namespace std;
// #define cin fein
// #define cout g
#define NMAX 1510
#define INF 10100000
#define pii pair<int,int>
#define piii pair<int, pii>
ifstream fein("dmin.in");
ofstream g("dmin.out");

long long int n, m, dist[NMAX], rez[NMAX],a, b, c;

vector<pii> l[NMAX];

struct edge
{
    int nod, cost;
    bool operator < (const edge a) const
    {
        return cost>a.cost;
    }
}nou, curent;

void dijk(int nod)
{
    for(int i=1;i<=n;i++)
    {
        dist[i]=INF;
    }
    dist[nod]=1;
    priority_queue<edge> d;
    curent.nod=nod;
    d.push(curent);
    while(!d.empty())
    {
        curent=d.top();
        int nc=curent.nod;
        d.pop();
        for(int i=0;i<l[nc].size();i++)
        {
            nou.nod=l[nc][i].first;
            nou.cost=dist[nc]*l[nc][i].second;
            int vc=nou.nod;
            if(dist[vc]>nou.cost)
            {
                dist[vc]=nou.cost;
                rez[vc]=1;
                d.push(nou);
            }
            else if(dist[vc]==nou.cost)
            {
                rez[vc]++;
                rez[vc]%=104659;
                d.push(nou);
            }

        }
    }
}


int main()
{
    fein>>n>>m;
    for(int i=1;i<=m;i++)
    {
        fein>>a>>b>>c;
        l[a].push_back(make_pair(b, c));
        l[b].push_back(make_pair(a, c));
    }
    dijk(1);
    for(int i=2;i<=n;i++)
    {
        g<<rez[i]<<" ";
    }

    return 0;
}