#include<stdio.h>
#include<queue>
#include<algorithm>
#include<math.h>
using namespace std;

#define MP make_pair
const int NMAX = 1505, mod = 104659, INF = 2e9;
const double eps = 1.e-10;
double dmin[NMAX];
int sol[NMAX];
bool vis[NMAX];

class cmp {
    public:
        bool operator () (int a, int b) const {
            return dmin[a] > dmin[b];
        }
};

priority_queue <int, vector <int>, cmp> q;

vector < pair <int, double> > graph[NMAX];

void dijkstra (int node) {
    sol[node] = 1;
    q.push(node);

    while(!q.empty()) {
        node = q.top();
        q.pop();
        
        if(vis[node]) continue;
        vis[node] = 1;
        
        for(int i = 0; i < graph[node].size(); ++ i)
            if(!vis[graph[node][i].first]) {
                int x = graph[node][i].first;
                double c = graph[node][i].second;

                if(dmin[node] + c < dmin[x]) {
                    dmin[x] = dmin[node] + c;
                    sol[x] = sol[node];
                    q.push(x);
                }
                else
                    if(fabs(dmin[node] + c - dmin[x]) < eps) 
                        sol[x] = (sol[node] + sol[x]) % mod;
                    
            }
    }
}

int main() {
    freopen("dmin.in", "r", stdin);
    freopen("dmin.out", "w", stdout);
    int n, m, x, y, c, i;

    scanf("%d%d", &n, &m);
    for(i = 1; i <= m; ++ i) {
        scanf("%d%d%d", &x, &y, &c);

        graph[x].push_back(MP(y, log(c)));
        graph[y].push_back(MP(x, log(c)));
    }

    for(i = 2; i <= n; ++ i)
        dmin[i] = 2e9;

    dijkstra(1);

    for(i = 2; i <= n; ++ i)
        printf("%d ", sol[i]);
    return 0;
}