#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;
        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)
{
    g[i][1].second=0;
    g[i][1].first=1;
    if(g[i][0].first<g.size())
    {
        do
        {
            int m=g[i][g[i][0].first].first;
            if(g[m][1].first==0)
            {
                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;
                col.push(g[i][g[i][0].first].first);
            }

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

            g[i][1].first=1;
            //afisare();

        }
        while(! col.empty() || g[i][0].first<g[i].size());
    }
}

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;
}
/// 4 3 11 12