#include <iostream>
#include <fstream>
#include <algorithm>
#include <cmath>
#include <queue>
#include <vector>

#define N 1505
#define inf 1 << 30
#define c first
#define y second
#define mod 104659
#define eps 0.0000000001

using namespace std;

ifstream fin("dmin.in");
ofstream fout("dmin.out");

int n, m;
typedef pair <double, int> nod;
vector <double> d(N, inf);
vector <nod> a[N];
vector <int> fr(N, 0);
vector <bool> viz(N);
queue <int> q;

int main()
{
    fin>>n>>m;
    while(m--)
    {
        int x, y;
        double c, c2;
        fin>>x>>y>>c;
        c2 = log10(c);
        a[x].push_back(nod(c2, y));
        a[y].push_back(nod(c2, x));
    }

    q.push(1);
    d[1] = 0;
    fr[1] = 1;
    viz[1] = 1;
    while(!q.empty())
    {
        int x = q.front();
        viz[x] = 0;
        q.pop();
        for(unsigned i=0; i<a[x].size(); i++)
            if(abs(d[x] + a[x][i].c - d[a[x][i].y]) <= eps)
            {
                fr[a[x][i].y] += fr[x];
                fr[a[x][i].y] %= mod;
            }
            else if(d[x] + a[x][i].c < d[a[x][i].y])
            {
                d[a[x][i].y] = d[x] + a[x][i].c;
                fr[a[x][i].y] = fr[x]%mod;
                if(!viz[a[x][i].y]) q.push(a[x][i].y), viz[a[x][i].y] = 1;;
            }
    }

    for(int i=2; i<=n; i++)
        fout<<fr[i]<<' ';
    return 0;
}