#include <iostream>
#include <fstream>
#include <vector>
#include <queue>

using namespace std;

ifstream in("dijkstra.in");
ofstream out("dijkstra.out");

vector<vector<pair<int,int> > > g;

queue<int> col;

int n,m,s;

void citire()
{
    int a,b,x;
    in>>n>>m;

    g.resize(n+1);
    for(a=1; a<=n; a++)
        g[a].push_back(make_pair(2,0)),g[a].push_back(make_pair(0,20001));

    n=0;
    while(in>>a)
    {
        in>>b;
        in>>x;
        /*if(g[a].empty())
            g[a].push_back(make_pair(2,0)),g[a].push_back(make_pair(0,20001));
        if(g[b].empty())
            g[b].push_back(make_pair(2,0)),g[b].push_back(make_pair(0,20001));*/
        g[a].push_back(make_pair(b,x));
        if(g[b][0].second==0)
            g[b][0].second=1,n++;
    }

}

void afisare()
{
    for(int l=1; l<g.size(); l++)
    {
        out<<l<<':'<<' ';
        for(int j=0; j<g[l].size(); j++)
            out<<g[l][j].first<<'*'<<g[l][j].second<<' ';
        out<<'\n';
    }
    out<<'\n';
}

void bfs(int i)
{
    s++;
    g[i][1].second=0;
    g[i][1].first=1;
    if(g[i][0].first<g.size())
    {
        while(s<n)
        {
            int m=g[i][g[i][0].first].first;
            if(g[i][g[i][0].first].second+g[i][1].second<g[m][1].second)
                g[m][1].second=g[i][g[i][0].first].second+g[i][1].second;

            if(g[m][1].first==0)
                col.push(g[i][g[i][0].first].first);

            g[i][0].first++;
            while(g[i][0].first>=g[i].size())
            {
                i=col.front();
                g[i][1].first=1;
                col.pop();
            }

            //afisare();

            s+=g[i][0].second;
            g[i][0].second=0;
        }
        int m=g[i][g[i][0].first].first;
        if(g[i][g[i][0].first].second+g[i][1].second<g[m][1].second)
            g[m][1].second=g[i][g[i][0].first].second+g[i][1].second;

    }
}

int main()
{
    citire();

    //afisare();

    bfs(1);

    //afisare();

    for(int i=2; i<g.size(); i++)
        if(g[i][1].second==20001)
            out<<0<<' ';
        else
            out<<g[i][1].second<<' ';

    return 0;
}