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

using namespace std;

const int NMax = 1510, MMax = 2510, MOD = 104659, INF = 2000000000;
const double EPS = 1e-9;
bool viz[NMax];
struct NOD
{
    int node;
    double cost;
    NOD() {node = 0; cost = 0.0;}
    NOD(const int node, const double cost)
    {
        this -> node = node;
        this -> cost = cost;
    }
};
vector <NOD> G[NMax];
int n, m;
int ans[NMax];
double d[NMax];

void Read()
{
    ifstream f("dmin.in");
    f>>n>>m;
    for (int i = 1; i <= m; ++i)
    {
        int x, y;
        double cost;
        f>>x>>y>>cost;
        cost = log(cost);
        G[x].push_back(NOD(y, cost));
        G[y].push_back(NOD(x, cost));
    }
    f.close();
}

inline bool cmp(const int &x, const int &y)
{
    return d[x] > d[y];
}

void Solve()
{
    vector <int> Q;
    for (int i = 1; i <= n; ++i)
        d[i] = INF;
    d[1] = 0;
    ans[1] = 1;
    Q.push_back(1);
    while (!Q.empty())
    {
        int node = Q[0];
        viz[node] = false;
        pop_heap(Q.begin(), Q.end(), cmp);
        Q.pop_back();
        for (vector <NOD> :: iterator it = G[node].begin(); it!=G[node].end(); ++it)
        {
            NOD aux = *it;
            if (d[aux.node] - d[node] - aux.cost > EPS)
            {
                d[aux.node] = d[node] + aux.cost;
                ans[aux.node] = ans[node];
                ans[aux.node] = ans[aux.node] >= MOD ? ans[aux.node] - MOD : ans[aux.node];
                if (!viz[aux.node])
                {
                    viz[aux.node] = true;
                    Q.push_back(aux.node);
                    push_heap(Q.begin(), Q.end(), cmp);
                }
            }
            else if (fabs(d[aux.node] - d[node] - aux.cost) <= EPS) /// is egale
            {
                ans[aux.node] += ans[node];
                ans[aux.node] = ans[aux.node] >= MOD ? ans[aux.node] - MOD : ans[aux.node];
            }
        }
    }
}

void Write()
{
    ofstream g("dmin.out");
    for (int i = 2; i<=n; ++i)
        g<<ans[i]<<" ";
    g<<"\n";
    g.close();
}

int main()
{
    Read();
    Solve();
    Write();
    return 0;
}