#include<bits/stdc++.h>
using namespace std;

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

const int DIM = 5e4 + 5;
const int INF = numeric_limits<int>::max();

int D[DIM], N, M;
vector< pair<int,int> > edge[DIM];
priority_queue< pair<int,int>,
                vector< pair<int,int> >,
                greater< pair<int,int> > > q;


int main(){

    fin >> N >> M;
    for( int i = 1; i <= M; i++ ){
        int x, y, z; fin >> x >> y >> z;
        edge[x].push_back( {y, z} );
    }

    for( int i = 1; i <= N; i++ )
        D[i] = INF;
    D[1] = 0;
    q.push( {0, 1} );
    while( !q.empty() ){
        pair<int,int> nod = q.top();
        q.pop();
        if( D[nod.second] != nod.first )
            continue;
        for( int i = 0; i < edge[nod.second].size(); i++ ){
            pair<int,int> v = edge[nod.second][i];
            if( D[v.first] > nod.first + v.second ){
                D[v.first] = nod.first + v.second;
                q.push( {D[v.first], v.first} );
            }
        }
    }

    for( int i = 2; i <= N; i++ )
        if( D[i] == INF )
            D[i] = 0;

    for( int i = 2; i <= N; i++ )
        fout << D[i] << " ";
    return 0;
}