#include <fstream>
#include <cmath>
#include <vector>
#include <bitset>
#include <queue>
#define eps 1.e-10
#define MOD 104659
#define DIM 1503

using namespace std;

int N,M;

vector <pair <int,double> > V[DIM];
bitset <DIM> inQueue;
queue <int> Q;
double D[DIM];
int RoadTrip[DIM];

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

int main(){

    fin >> N >> M;

    while(M--){
        int x,y,c;
        fin >> x >> y >> c;
        V[x].push_back(make_pair(y,log10(c)));
        V[y].push_back(make_pair(x,log10(c)));
    }

    for(int i=2;i<=N;i++)
        D[i] = 0x3f3f3f3f;

    inQueue[1]=1;
    Q.push(1);
    RoadTrip[1]=1;
    while(!Q.empty()){

        int node = Q.front();
        inQueue[node]=0;
        Q.pop();
        for(std::vector <pair <int,double> >::iterator it = V[node].begin(); it != V[node].end() ; it ++){
            if(D[it->first] - (D[node] + it->second) >= eps){
                D[it->first] = D[node] + it->second;
                RoadTrip[it->first] = RoadTrip[node];
                if(!inQueue[it->first]){
                    Q.push(it->first);
                    inQueue[it->first]=1;
                }
            }
            else
                if(abs(D[it->first] - (D[node] + it->second)) < eps){
                    RoadTrip[it->first] = (RoadTrip[it->first] + RoadTrip[node])%MOD;
                }
        }

    }

    for(int i=2;i<=N;i++)
        fout << RoadTrip[i] << " ";

    fout << "\n" ;

}