#include <bits/stdc++.h>

using namespace std;
ifstream in("dmin.in");
ofstream out("dmin.out");
const int nx=1502;
struct muchie
{
    int nod;
    int cost;
};
vector < muchie > v[nx];
int n,m,i,j,c;
struct big
{
    int nr;
    int v[102];
};
vector < big > dist;
vector < int > sol;
int compare (big a, big b)
{
    if(a.nr>b.nr) return 1;
    if(a.nr<b.nr) return -1;
    for(int i=a.nr; i; i--)
    {
        if(a.v[i]>b.v[i]) return 1;
        if(a.v[i]<b.v[i]) return -1;
    }
    return 0;
}
big times (big a, int x)
{
    big rez=a;
    long long t=0;
    for(int i=1; i<=rez.nr; i++)
    {
        rez.v[i]=rez.v[i]*x + t;
        t=rez.v[i]/10;
        rez.v[i]%=10;
    }
    while(t)
        rez.v[++rez.nr]=t%10,t/=10;
    return rez;
}
void bfs ()
{
    queue < int > q;
    q.push(1);
    dist[1].nr=1;
    dist[1].v[1]=1;
    sol[1]=1;
    big a;
    int val;
    while(!q.empty())
    {
        int x=q.front();
        q.pop();
        for(vector < muchie > :: iterator it=v[x].begin(); it!=v[x].end(); it++)
        {
            a=times(dist[x],it->cost);
            val=compare(dist[it->nod],a);
            if(val==1)
            {
                dist[it->nod]=a;
                sol[it->nod]=1;
                q.push(it->nod);
            }
            else if(val==0)
            {
                sol[it->nod]++;
                q.push(it->nod);
            }
        }
    }
    for(int i=2; i<=n; i++)
        out<<sol[i]<<' ';
}
int main()
{
    in>>n>>m;
    big nrmax;
    nrmax.nr=102;
    for(i=0; i<=102; i++)
        nrmax.v[i]=9;
    dist= vector < big > (n+1,nrmax);
    sol= vector < int > (n+1,0);
    for(;m;m--)
    {
        in>>i>>j>>c;
        v[i].push_back({j,c});
        v[j].push_back({i,c});
    }
    bfs();
    return 0;
}