#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));

    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));
    }
}

void bfs(int i)
{
    g[i][1].second=0;
    g[i][1].first=1;
    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();
        }

        /*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';

        s++;
    }
}

int main()
{
    citire();

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

    bfs(1);

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

    return 0;
}