#include <bits/stdc++.h>

using namespace std;

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

#define Nmax 50005
#define pb push_back
#define MOD 104659


const int INF=1e5;
int x,y,n,m,c1,L[Nmax];
bool viz[Nmax];
const double eps = 1e-6;

vector <pair <int,int> > v[Nmax];
vector < int > T;

int D[Nmax];

int cmp(const int&a, const int&b){
    return(L[a] > L[b]);
}

void dijkstra(){

    int node;
    T.pb(1);
    make_heap(T.begin(),T.end(),cmp);
    while(!T.empty()){
        node=T.front();
        pop_heap(T.begin(),T.end(),cmp);
        T.pop_back();
        for(int i=0;i<v[node].size();i++){
            if(L[v[node][i].first] > L[node] + v[node][i].second){
                L[v[node][i].first] = L[node] + v[node][i].second;
                T.pb(v[node][i].first);
                push_heap(T.begin(),T.end(),cmp);
        }

    }
    }


}

#define Mod(a) (max(a, -a))

int Solve(int node){

        if(viz[node])return D[node];
        viz[node]=1;
        for(int i=0;i<v[node].size();i++)
            if(Mod(L[v[node][i].first] - L[node] + v[node][i].second) < eps)
                D[node]+=Solve(v[node][i].first),D[node]%=MOD;
        return D[node];


}

int main(){

    in>>n>>m;

    for(int i=1;i<=m;i++)
    {
        in>>x>>y>>c1;
        v[x].pb({y,log(c1)});
        v[y].pb({x,log(c1)});

    }
     for(int i=2;i<=n;i++)
        L[i]=INF;
    dijkstra();
    viz[1]=1;
    D[1]=1;
    for(int i=2;i<=n;i++){
        D[i]=Solve(i);
        }
    for(int i=2;i<=n;i++)
        out<<D[i]<<" ";
    for(int i=2;i<=n;i++){
            cout<<L[i]<<" "
    ;}
    return 0;
}