#include <bits/stdc++.h>
#define prec 1.00000000000
#define eps 0.00000000001
#define inf 100000000000
#define mod 104659

using namespace std;

double abss(double x)
{
    if (x < 0)
        return -prec * x;
    return prec * x;
}
struct dik
{
    int nod;
    int fr;
    double cost;
    bool operator<(const dik &a) const
    {
        return cost > a.cost;
    }
};
vector<dik> ad[1501];
int fminn[1501];
double f[1501];
priority_queue<dik> pq;

void dijkstra()
{
    int i;
    dik a, aux;
    while (!pq.empty())
    {
        a = pq.top();
        pq.pop();
        if (abss(f[a.nod] - a.cost) <= eps && a.fr == fminn[a.nod])
        {
            for (i = 0; i < ad[a.nod].size(); i++)
            {
                if (f[ad[a.nod][i].nod] - (a.cost + ad[a.nod][i].cost) > eps)
                {
                    aux.cost = a.cost + ad[a.nod][i].cost, aux.nod = ad[a.nod][i].nod, aux.fr = a.fr % mod;
                    f[aux.nod] = aux.cost, fminn[aux.nod] = a.fr % mod;
                    pq.push(aux);
                }
                else if (abss(a.cost + ad[a.nod][i].cost - f[ad[a.nod][i].nod]) <= eps)
                {
                    fminn[ad[a.nod][i].nod] += a.fr;
                    fminn[ad[a.nod][i].nod] %= mod;
                    aux.cost = a.cost + ad[a.nod][i].cost, aux.nod = ad[a.nod][i].nod, aux.fr = fminn[ad[a.nod][i].nod];
                    pq.push(aux);
                }
            }
        }
    }
}

int main()
{
    ifstream cin("dmin.in");
    ofstream cout("dmin.out");
    int n, m, i, a, b, c;
    double logc;
    cin >> n >> m;
    for (i = 1; i <= n; i++)
        f[i] = inf;
    for (i = 0; i < m; i++)
    {
        cin >> a >> b >> c;
        logc = prec * log2(c);
        ad[a].push_back({b, 0, logc});
        ad[b].push_back({a, 0, logc});
    }
    pq.push({1, 1, 0}), f[1] = 0, fminn[1] = 1;
    dijkstra();
    for (i = 2; i <= n; i++)
        cout << fminn[i] << " ";
    return 0;
}