#include <bits/stdc++.h>

using namespace std;

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

const long double er=1e-10;
const int mod=104659;
int n,m;
vector<vector<pair<int,long double>>>a;
vector<int>nr;
vector<long double>cm;

struct str {
    int nod;
    long double cost;
    bool operator < (const str &aux)const {
        return cost>aux.cost;
    }
};


void dijkstra(){
    priority_queue<str>pq;
    pq.push({1,0});
    while (!pq.empty()) {
        int nod=pq.top().nod;
        long double cost=pq.top().cost;
        pq.pop();
        if (cost>cm[nod]) continue;
        for (auto f:a[nod]){
            cout<<abs((cm[nod]+f.second)-cm[f.first])<<" ";
            if (cm[nod]+f.second<cm[f.first]-er) {
                nr[f.first]=nr[nod];
                cm[f.first]=cm[nod]+f.second;
                pq.push({f.first,cm[f.first]});
            }else if (abs((cm[nod]+f.second)-cm[f.first])<er) {
                nr[f.first]+=nr[nod];
                nr[f.first]%=mod;
            }
        }
    }
}


int main() {
    fin>>n>>m;
    a.resize(n+1);
    nr.resize(n+1);
    cm.resize(n+1,1e18);
    int na,nb;
    long double nc;
    for (int i=1;i<=m;i++) {
        fin>>na>>nb>>nc;
        nc=log(nc);
        a[na].push_back({nb,nc});
        a[nb].push_back({na,nc});
    }
    nr[1]=1;
    cm[1]=0;
    dijkstra();
    for (int i=2;i<=n;i++) fout<<nr[i]<<" ";
    return 0;
}