#include <bits/stdc++.h>

using namespace std;
const int MOD = 104659;
ifstream in("dmin.in");
ofstream out("dmin.out");
int viz[1505],dist[1505];
vector< pair<int,int> > v[1505];

int main()
{
    int n,m;
    in >> n >> m;
    for (int i = 1; i<=m; i++)
    {
        int x,y,z;
        in >> x >> y >> z;
        v[x].push_back({y,z});
        v[y].push_back({x,z});
    }
    viz[1] = 1;
    queue<int> q;
    q.push(1);
    while (!q.empty())
    {
        int now = q.front();
        q.pop();
        for (auto it: v[now])
        {
            int next = it.first, cost = it.second, val = (dist[now]+cost)%MOD;
            if (!viz[next])
            {
                viz[next] = 1;
                dist[next] = val;
                q.push(next);
            }
            else if (dist[next] > val)
            {
                viz[next] = 1;
                dist[next] = val;
                q.push(next);
            }
            else if (dist[next] == dist[now]+cost)
            {
                viz[next]++;
                q.push(next);
            }
        }
    }
    for (int i = 2; i<=n; i++)
        out << viz[i] << " ";
}