#include <fstream>
#include <queue>
#include <vector>
#include <cmath>
#include <cstdlib>

#define rint register int
#define mp make_pair
#define pb push_back
#define f first
#define s second
#define eps 0.0000000001

const char IN[]  = "dmin.in";
const char OUT[] = "dmin.out";
const int MAX = 1514;
const int MOD = 104659;
const int INF = 1<<30;

using namespace std;

ifstream fin(IN);
ofstream fout(OUT);

typedef std:: pair<int,double> P;
vector <P> gr[MAX];
struct cmp{
    bool operator()(const P &a,const P &b){
        return ( a.s>b.s );
    }
};
priority_queue <P,vector<P>,cmp> h;

double d[MAX];
int fr[MAX],n;
void dijkstra( );
int main( )
{
    int m;
    fin >> n >> m;
    while(m--){
        int x,y;
        double c,tr;
        fin >> x >> y >> c;
        tr=log10(c);
        gr[x].pb( mp( y , tr ) );
        gr[y].pb( mp ( x , tr ) );
    }
    for(rint i=2;i<=n;++i)d[i]=INF;
    dijkstra();
    for(int i=2; i<=n; i++)
        fout<<fr[i]<<' ';
    return 0;
}
void dijkstra( )
{
    h.push(mp(1,0));
    d[1]=0;
    fr[1]=1;
    while(!h.empty()){
        int fata=h.top().f;
        double cost=h.top().s;
        h.pop();
        for(rint i=0;i<(int)gr[fata].size();++i)
            if(abs(cost + gr[fata][i].s - d[gr[fata][i].f])<=eps){
                fr[gr[fata][i].f] += fr[fata];
                fr[gr[fata][i].f] %= MOD;
            }
            else if(cost + gr[fata][i].s < d[gr[fata][i].f])
            {
                d[gr[fata][i].f] = cost + gr[fata][i].s;
                fr[gr[fata][i].f] = fr[fata]%MOD;
                h.push(mp(gr[fata][i].f,d[gr[fata][i].f]));
            }
    }
}