#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");

struct nod
{
    int x;
    int y;
    double c;
};
int n, m, x, y, k;
double cst;
nod t[2*M];
int tart[N], nr[N], start[N];
bool viz[N];
double cost[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[man].c < cost[t[man].x] )
            {
                cost[t[man].x] = cost[om] + t[man].c;
                nr[t[man].x] = nr[om] % mod;
                if( !viz[t[man].x])
                {
                    viz[t[man].x] = 1;
                    c.push(t[man].x);
                }
            }
            else
                if(cost[om] + t[man].c == cost[t[man].x])
                    nr[t[man].x] = (nr[t[man].x] + nr[om]) % mod;
            man = t[man].y;
        }
        c.pop();
    }
}
int main()
{
    fin >> n >> m;
    while(fin >> x >> y >> cst)
    {
        k++;
        t[k].x = y;
        t[k].y = start[x];
        start[x] = k;

        k++;
        t[k].x = x;
        t[k].y = start[y];
        start[y] = k;

        t[k].c = t[k-1].c = cst;
    }

    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;
}