#include<cstdio>
#include<vector>
#include<cmath>
#include<queue>
#define MAXN 1510
#define EPS 1e-8
#define MOD 104659
#define INF 1000000000
using namespace std;
vector<pair<int,double> > g[MAXN];
int n,m;
double best[MAXN];
int dp[MAXN];
struct Compare{
    bool operator()(pair<int,double> a,pair<int,double> b){
        return a.second>b.second;
    }
};
priority_queue<pair<int,double>,vector<pair<int,double> >,Compare> Heap;
void Dijkstra(){
    int i,node;
    double cost;
    for(i=2;i<=n;i++)
        best[i]=INF;
    best[1]=0;
    dp[1]=1;
    Heap.push(make_pair(1,0));
    while(!Heap.empty()){
        node=Heap.top().first;
        cost=Heap.top().second;
        Heap.pop();
        for(i=0;i<g[node].size();i++){
            if(best[g[node][i].first]-EPS>=cost+g[node][i].second){
                best[g[node][i].first]=cost+g[node][i].second;
                dp[g[node][i].first]=dp[node];
                Heap.push(make_pair(g[node][i].first,best[g[node][i].first]));
            }
            else
                if(fabs(best[g[node][i].first]-cost-g[node][i].second)<=EPS){
                    dp[g[node][i].first]+=dp[node];
                    if(dp[g[node][i].first]>=MOD)
                        dp[g[node][i].first]-=MOD;
                }
        }
    }
}
int main(){
    freopen("dmin.in","r",stdin);
    freopen("dmin.out","w",stdout);
    int i,a,b;
    double c;
    scanf("%d%d",&n,&m);
    for(i=1;i<=m;i++){
        scanf("%d%d%lf",&a,&b,&c);
        g[a].push_back(make_pair(b,log10(c)));
        g[b].push_back(make_pair(a,log10(c)));
    }
    Dijkstra();
    for(i=2;i<=n;i++)
        printf("%d ",dp[i]);
    return 0;
}