#include <fstream>
#include <queue>
#include <cmath>
#include <iostream>
using namespace std;
 
ifstream fin ("dmin.in");
ofstream fout ("dmin.out");
 
#define N 1505
#define xx first
#define yy second
#define MOD 104659
#define NEXT 2e9
 
typedef long double def;
typedef pair <def, int> nod;
typedef pair <nod, int> all;
 
const def oo = 1e5;
const def er = 1e-8;
 
vector <nod> g[N];
int f[N], n, m;
def d[N];
priority_queue <all, vector <all>, greater <all> > H;
 
int main() {
    fin >> n >> m;
    while (m--) {
        int x, y; def z;
        fin >> x >> y >> z;
        g[x].push_back (nod (log(z), y));
        g[y].push_back (nod (log(z), x));
    }
    fin.close();
    for (int i = 1; i <= n; ++i)
        d[i] = oo;
    H.push(all (nod (0, 1), 1));
    while (H.size()) {
        def crt = H.top().xx.xx; int x = H.top().xx.yy, fr = H.top().yy; H.pop();
        if (d[x] != oo && (d[x] < crt - er || d[x] > crt + er))
            continue;
        if (d[x] == oo) {
            d[x] = crt;
            H.push(all (nod(crt + er, x), NEXT));
        }
        if (fr != NEXT) {
            f[x] = (f[x] + fr) % MOD;
            continue;
        }
        for (vector <nod> :: iterator it = g[x].begin(); it != g[x].end(); ++it)
            if (d[(*it).yy] == oo)
                H.push(all (nod (d[x] + (*it).xx, (*it).yy), f[x]));
    }
    for (int i = 2; i <= n; ++i)
        fout << f[i] << " ";
    fout.close();
}