#include<fstream>
#include<vector>
#define maxn 1505
#define lmax 2000000000
#define r 104659
#define rr 1234567899

using namespace std;

vector< pair<int,int> > v[maxn];
vector<int> lant[maxn];
int h[maxn], pos[maxn], n, num[maxn];
long long a[maxn];
ofstream g("dmin.out");

void up(int k){
    int x = h[k];
    while (k > 1 && a[h[k/2]] > a[x]) {
        h[k] = h[k/2];
        pos[h[k]] = k;
        k = k/2;
    }
    h[k] = x;
    pos[x] = k;   
}

void down(int k){
    int son = 1, aux;
    while (son != 0){
        son = 0;
        if (k*2 <= n){
            son = k*2;
            if (k*2+1 <= n && a[h[k*2]] > a[h[k*2+1]])
                son = k*2+1;
            if (son != 0 && a[h[son]] > a[h[k]])
                son = 0;
        }
        if (son != 0){
            aux = h[son];
            h[son] = h[k];
            h[k] = aux;
            pos[h[k]] = k;
            pos[h[son]] = son;
            k = son;     
        }
    }    
}

void dfs(int nod){
    int nr = 0;
    for (int i = 0; i < lant[nod].size(); i++){
        if (num[lant[nod][i]] == 0)
            dfs(num[lant[nod][i]]);  
        nr = (nr+num[lant[nod][i]])%r;
    }
    num[nod] = nr;
}

int main(){
    ifstream f("dmin.in");
    
    int m, i, j, nodm, dist, poz, k1;
    pair<int, int> k;
    f>>n>>m;
    for (i = 1; i <= m; i++){
        f>>j>>k1>>dist;
        v[j].push_back(make_pair(k1, dist));
        v[k1].push_back(make_pair(j, dist));
    }
    
    h[1] = 1;
    a[1] = 0;
    pos[1] = 1;
    for (i = 2; i <= n; i++){
        h[i] = i;
        a[i] = lmax;
        pos[i] = i;
    }
    int nr = n;
    while (n > 0){
        nodm = h[1];
        h[1] = h[n];
        n--;
        down(1);
        for (i = 0; i < v[nodm].size(); i++){
            k = v[nodm][i];
            if (a[k.first] > a[nodm] + k.second){
                a[k.first] = a[nodm] + k.second;
                poz = pos[k.first];
                up(poz);
                lant[k.first].push_back(nodm);
            }
            else 
                if (a[k.first] == a[nodm] + k.second)
                    lant[k.first].push_back(nodm);
        }               
    } 
    
    num[1] = 1;
    for (i = 2; i <= nr; i++)
        if (num[i] == 0)
            dfs(i); 
           
    for (i = 2; i <= nr; i++)
        g<<num[i]<<" ";  
    
    return 0;
}