#include <bits/stdc++.h>
#define N 1505
#define MOD 104659
#define oo 1e9
using namespace std;
ifstream fin("dmin.in");
ofstream fout("dmin.out");
int n,m,d[N],nr[N];
bool viz[N];
struct muchie
{
    int nod,cost;
    bool operator < (const muchie x) const
    {
        return x.cost<cost;
    }
};
int compute(int x,int y)
{
    return 1ll*x*y%MOD;
}
vector<muchie>g[N];
priority_queue<muchie>pq;
void Dijkstra()
{
    int nod,cost;
    pq.push({1,1});
    fill(d+1,d+n+1,oo);
    while(!pq.empty())
    {
        nod=pq.top().nod;
        cost=pq.top().cost;
        pq.pop();
        if(cost<d[nod]) d[nod]=cost;
        else continue;
        for(auto x:g[nod])
        if(compute(d[nod],x.cost)<d[x.nod]) pq.push({x.nod,compute(d[nod],x.cost)});
    }
}
void DFS(int x)
{
    viz[x]=1;
    for(auto i:g[x])
        if(!viz[i.nod])
    {
        if(compute(d[x],i.cost)==d[i.nod]) nr[i.nod]+=nr[x];
        DFS(i.nod);
    }
}
void BFS()
{
    queue<int>q;
    q.push(1);
    viz[1]=1;
    while(!q.empty())
    {
        int k=q.front();
        q.pop();cout<<k<<": ";
        for(muchie i:g[k])
        {
            if(compute(d[k],i.cost)==d[i.nod]) nr[i.nod]+=nr[k];nr[i.nod]%=MOD;
            if(!viz[i.nod])viz[i.nod]=1,q.push(i.nod);cout<<i.nod<<" ";
        }
        cout<<"\n";
    }
}
int main()
{
    int x,y,c,i;
    fin>>n>>m;
    while(m--)
        fin>>x>>y>>c,
        g[x].push_back({y,c}),
        g[y].push_back({x,c});
    Dijkstra();
    for(i=1;i<=n;i++) cout<<d[i]<<" ";
    nr[1]=1;BFS();//DFS(1);
    for(i=2;i<=n;i++) fout<<nr[i]<<" ";
    return 0;
}