#include <fstream>
#include <vector>
#include <queue>
#include <cmath>
#define NM 1510
#define MOD 104659
#define EPS 1e-8
#define INF 999999999
#define node first
#define cost second

using namespace std;

ifstream f("dmin.in");
ofstream g("dmin.out");

bool Equal (double a, double b)
{
    return fabs(a-b)<EPS;
}

typedef pair<int, double> PI;

struct CMP
{
    bool operator () (const PI& a, const PI& b) const
    {
        return a.cost>b.cost;
    }
};

priority_queue<PI, vector<PI>, CMP> Q;
int N, M;
vector <PI> G[NM];
double Dist[NM];
int DP[NM];

void Read ()
{
    f >> N >> M;
    for (int i=1; i<=M; i++)
    {
        int a, b, c;
        f >> a >> b >> c;
        G[a].push_back(make_pair(b, log(1.0*c)));
        G[b].push_back(make_pair(a, log(1.0*c)));
    }

    f.close();
}

void DoDijkstra ()
{
    vector<PI>::iterator it;
    int i, node;
    double cost;

    for (i=1; i<=N; i++)
        Dist[i]=INF;

    Dist[1]=0;
    DP[1]=1;
    Q.push(make_pair(1, 0));

    while (!Q.empty())
    {
        node=Q.top().node;
        cost=Q.top().cost;
        Q.pop();

        if (!Equal(Dist[node], cost))
            continue;

        for (it=G[node].begin(); it!=G[node].end(); ++it)
            if (cost+it->cost<Dist[it->node] || Equal(cost+it->cost, Dist[it->node]))
            {
                if (cost+it->cost<=Dist[it->node]-EPS)
                {
                    Dist[it->node]=cost+it->cost;
                    Q.push(make_pair(it->node, Dist[it->node]));
                    DP[it->node]=0;
                }
                DP[it->node]+=DP[node];
                if (DP[it->node]>=MOD)
                    DP[it->node]-=MOD;
            }
    }
}

void Print ()
{
    for (int i=2; i<=N; i++)
        g << DP[i] << ' ';
    g << '\n';

    g.close();
}

int main ()
{
    Read();
    DoDijkstra();
    Print();

    return 0;
}