#include <iostream>
#include <fstream>
#include <queue>
using namespace std;
#define N 1501
#define M 2500
#define mod 104659
#define inf 999999999
ifstream fin("dmin.in");
ofstream fout("dmin.out");

int n, m, x, y, cst, k;
int t[3][2*M], start[N], viz[N], cost[N], nr[N];
queue <int> c;

void ford()
{
    int om, man;
    c.push(1);
    viz[1] = 1;
    nr[1] = 1;
    while( !c.empty() )
    {
        om = c.front();
        man = start[om];
        viz[om] = 0;
        while(man)
        {
            if(cost[om] + t[2][man] < cost[t[0][man]] )
            {
                cost[t[0][man]] = cost[om] + t[2][man];
                nr[t[0][man]] = nr[om] % mod;
                if( !viz[t[0][man]])
                {
                    viz[t[0][man]] = 1;
                    c.push(t[0][man]);
                }
            }
            else
                if(cost[om] + t[2][man] == cost[t[0][man]])
                    nr[t[0][man]] = (nr[t[0][man]] + nr[om]) % mod;
            man = t[1][man];
        }
        c.pop();
    }
}
int main()
{
    fin >> n >> m;
    while(fin >> x >> y >> cst)
    {
        k++;
        t[0][k] = y;
        t[1][k] = start[x];
        start[x] = k;

        k++;
        t[0][k] = x;
        t[1][k] = start[y];
        start[y] = k;

        t[2][k] = t[2][k-1] = cst % mod;
    }

    for(int i=2; i<=n; i++)
        cost[i] = inf;
    cost[1] = 0;

    ford();

    for(int i=2; i<=n; i++)
        fout << nr[i] % mod << " ";
    return 0;
}