#include <iostream>
#include <fstream>
#include <vector>
#include <vector>
#include <set>
#define MAX 1500000000005
#define mod 104659

using namespace std;

ifstream f("dmin.in");
ofstream g("dmin.out");

long long n, m, from, to, cost, energii[1505], nr[1505];

bool onq[1505];

vector<pair<int, int > >graph[1505];

bool operator<(pair<int,int>p1, pair<int,int>p2)
{
    if (p1.second==p2.second)
        return p1.first<p2.first;
    return p1.second<p2.second;
}

set<pair<int,int> >q;

void citire()
{
    f >> n >> m;
    for (int i=1; i<=m; i++)
    {
        f >> from >> to >> cost;
        graph[from].push_back(make_pair(to,cost));
        graph[to].push_back(make_pair(from,cost));

    }
}

void dijkstra()
{
    for (int i=2; i<=n; i++)
    {
        energii[i]=MAX;
    }
    nr[1]=1;
    q.insert({1,0});
    onq[1]=true;
    while (!q.empty())
    {
        int nod=q.begin()->first;
        onq[nod]=false;
        q.erase(q.begin());
        for (auto &v:graph[nod])
        {
            int vecin=v.first;
            int cost=v.second;
            if (energii[nod]+cost<energii[vecin])
            {
                energii[vecin]=energii[nod]+cost;
                nr[vecin]=nr[nod];
                if (!onq[vecin]) {
                    q.insert({vecin, energii[vecin]});
                    onq[vecin]=true;
                }
            }
            else if (energii[nod]+cost==energii[vecin])
            {
                nr[vecin]+=nr[nod];
                nr[vecin]%=mod;

            }
        }
    }
    for (int i=2; i<=n; i++)
        g << nr[i] <<' ';
}

int main() {
    citire();
    dijkstra();
    return 0;
}