#include <bits/stdc++.h>

using namespace std;
ifstream fin ("dmin.in");
ofstream fout ("dmin.out");
const int MOD = 104659;
const int MAX = 1505;
const int INF = 1e9;
set < pair <int,int> > T;
vector < pair <int,int> > G[MAX];
struct fac{
int c,d,r;
}D[MAX];
inline void solve()
{
    int cost,nod;
    T.insert({0,1});
    D[1].d = 1;
    while(!T.empty()){
        cost = (*T.begin()).first;
        nod = (*T.begin()).second;
        T.erase(*T.begin());
        for(int i = 0; i < G[nod].size(); i++){
            if(D[G[nod][i].second].r >= D[nod].r + (D[nod].d*G[nod][i].first)/MOD && D[G[nod][i].second].d >  (D[nod].d*G[nod][i].first)%MOD){
                D[G[nod][i].second].r = D[nod].r + (D[nod].d*G[nod][i].first)/MOD;
                D[G[nod][i].second].d = (D[nod].d*G[nod][i].first)%MOD;
                D[G[nod][i].second].c++;
                T.insert({D[G[nod][i].second].r,G[nod][i].second});
            }
            else
                if(D[G[nod][i].second].r == D[nod].r + (D[nod].d*G[nod][i].first)/MOD && D[G[nod][i].second].d ==  (D[nod].d*G[nod][i].first)%MOD){
                D[G[nod][i].second].c ++;
                T.insert({D[G[nod][i].second].r,G[nod][i].second});
                }
        }
    }
}
int main()
{
    int n,m,x,y,c;
    fin >> n >> m;
    for(int i = 1; i <= m; i++){
        fin >> x >> y >> c;
        G[x].push_back({c,y});
        G[y].push_back({c,x});
    }
    for(int i = 2; i <= n; i++)
        D[i].d = INF,D[i].r = INF;
    solve;
    for(int i = 2; i <= n; i++)
        fout << D[i].c << " ";
    return 0;
}