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

using namespace std;

ifstream fin("scmax.in");
ofstream fout ("scmax.out");


const int NMAX = 50001, MMAX = 250001, INF = 1000000001;
int N,M;
vector < int > Ad[NMAX], values[NMAX];
int dist[NMAX];
bool vis[NMAX];

void Dijkstra (int nod)
{
    for (int i = 1; i <= N; ++i)
    {
        dist[i] = INF;
    }
    priority_queue< pair < int, int > , vector < pair < int, int > >, greater < pair < int, int > >  > H;
    dist[nod] = 0;
    H.push( {dist[nod], nod} );
 
    while( !H.empty() ){
        nod = H.top().second;
        H.pop();
 
        if( vis[nod] ) continue;
        else vis[nod] = 1;
 
        for( int i = 0; i < Ad[nod].size(); ++i ){
 
            int w = Ad[nod][i];
            int dw = values[nod][i];
 
            if( dist[w] > dist[nod] + dw ){
                dist[w] = dist[nod] + dw;
                H.push( {dist [w], w} );
            }
        }
    }
 
}
int main ()
{
    fin >> N >> M;
    for (int i = 1; i <= M; ++i)
    {
        int x,y,c;
        fin >> x >> y >> c;
        Ad[x].push_back(y);
        values[x].push_back(c);
    }
    Dijkstra(1);
    for (int i = 2; i <= N; ++i)
    {
        if (dist[i] != INF) fout << dist[i] << ' ';
        else fout << 0 << ' ';
    }
}