#include <fstream>
#include <vector>
#include <math.h>
#define INF 1000000000
#define MOD 104659
using namespace std;
ifstream fin("dmin.in");
ofstream fout("dmin.out");
int n, m, x, y, coada[300000], p, u, nr[1510];
vector< pair<int, double> > g[1510];
double di, d[1510], epsilon=0.0000001;
bool incoada[1510];

int main()
{
    fin>>n>>m;

    for(int i=1;i<=m;i++)
    {
        fin>>x>>y>>di;
        g[x].push_back(make_pair(y, log10(di)));
        g[y].push_back(make_pair(x, log10(di)));
    }

    for(int i=2;i<=n;i++)
        d[i]=INF;

    coada[1]=1;
    nr[1]=1;
    p=u=1;
    while(p<=u)
    {
        for(int i=0;i<g[coada[p]].size();i++)
            if(d[g[coada[p]][i].first]>d[coada[p]]+g[coada[p]][i].second && d[g[coada[p]][i].first]-(d[coada[p]]+g[coada[p]][i].second)>epsilon)
        {
            d[g[coada[p]][i].first]=d[coada[p]]+g[coada[p]][i].second;
            nr[g[coada[p]][i].first]=nr[coada[p]]%MOD;
            if(!incoada[g[coada[p]][i].first])
            {
                incoada[g[coada[p]][i].first]=1;
                coada[++u]=g[coada[p]][i].first;
            }
        }
        else
            if((d[g[coada[p]][i].first]-(d[coada[p]]+g[coada[p]][i].second)<epsilon)&&(d[g[coada[p]][i].first]-(d[coada[p]]+g[coada[p]][i].second)>-epsilon))
        {
            nr[g[coada[p]][i].first]=(nr[g[coada[p]][i].first]+nr[coada[p]])%MOD;
            if(!incoada[g[coada[p]][i].first])
            {
                incoada[g[coada[p]][i].first]=1;
                coada[++u]=g[coada[p]][i].first;
            }
        }

        incoada[coada[p]]=0;
        p++;
    }

    for(int i=2;i<=n;i++)
        fout<<nr[i]<<' ';

    return 0;
}