#include<bits/stdc++.h>
#define pb push_back

using namespace std;

ifstream f("dijkstra.in");
ofstream g("dijkstra.out");
const int INF = 0x3f3f3f3f;

int n, m;
int dp[50001];
vector< pair<int, int> >G[50001];
set< pair<int, int> >H;

int main()
{
    f >> n >> m;
    for(int i = 1 ; i <= m ; ++i)
    {
        int x, y, c;
        f >> x >> y >> c;
        G[x].pb({y, c});
    }
    memset(dp, INF, sizeof(dp));

    dp[ 1 ] = 0;

    H.insert({0, 1});
    while(!H.empty())
    {
        int node = H.begin()->second;
        H.erase(H.begin());
        for(vector< pair< int, int > >::iterator it = G[node].begin(); it != G[node].end(); ++it)
        {

            if(dp[it->first] > dp[node] + it->second)
            {


                if(dp[it->first] != INF)
                {
                    H.erase(H.find({dp[it->first], it->first}));
                }
                H.insert({dp[node] + it->second, it->first});
                dp[it->first] = dp[node] + it->second;
            }
        }
    }
    for(int i = 2 ; i <= n ; ++i)
        if(dp[ i ] == INF)
            g << 0 << ' ';
        else
            g << dp[ i ] << ' ';
}