#include <fstream>
#include <vector>
#include <queue>
using namespace std;
ifstream in("dmin.in");
ofstream out("dmin.out");

const int oo = (1 << 30);
const int NMAX = 1501;

int d[NMAX];
int d2[NMAX];
int n,m;
bool inCoada[NMAX];

struct _compare{

    bool operator()(int x,int y)
    {
        return d[x] > d[y];
    }
};
priority_queue < int, vector<int>, _compare> tail;
vector < pair < int, int > > laturi[NMAX];

void Citire()
{
    int x,y,c;
    in>>n>>m;
    for(int i=0;i<m;i++)
    {
    in>>x>>y>>c;
    laturi[x].push_back(make_pair(y,c));
    }
    for(int i=1;i<=n;i++)d[i] = oo;
}
void Afisare()
{
    for(int i=2;i<=n;i++)
    {
        out<<d2[i]<<" ";
    }
    out<<"\n";
}
void Dijkstra(int nod_start)
{
    d[nod_start] = 1;
    tail.push(nod_start);
    inCoada[nod_start] = true;
    int nod_cur;
    while(!tail.empty()){
    nod_cur = tail.top();
    tail.pop();
    inCoada[nod_cur] = false;
    for(size_t i=0;i<laturi[nod_cur].size();i++)
    {
        int cost = laturi[nod_cur][i].second;
        int vecin = laturi[nod_cur][i].first;
        d2[vecin]++;

        if(d[vecin] > d[nod_cur] * cost){
            d[vecin] = d[nod_cur] * cost;
            d2[vecin]=1;
        }
         tail.push(vecin);
            inCoada[vecin] = true;
    }
    }
}
int main()
{
Citire();
Dijkstra(1);
Afisare();
}