#include <bits/stdc++.h>
#define DIM 50005
#define INF 0x7fffffff
using namespace std;

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

int n, m;
vector< pair<int, int> > neighbours[DIM];
set< pair<int, int> > edges;
int distances[DIM];

int main () {

    in>>n>>m;
    for( int i = 1; i <= m; i++ )
    {
        int from, to, cost;
        in>>from>>to>>cost;

        neighbours[from].push_back( {to, cost} );
    }

    for( int i = 2; i <= n; i++ )
        distances[i] = INF;

    edges.insert( {0, 1} );
    while( !edges.empty() )
    {
        int node = edges.begin()->second;
        edges.erase( edges.begin() );

        for( pair<int, int> neighbour : neighbours[node] )
            if( distances[neighbour.first] > distances[node] + neighbour.second )
            {
                edges.erase( {distances[neighbour.first], neighbour.first} );
                distances[neighbour.first] = distances[node] + neighbour.second;
                edges.insert( {distances[neighbour.first], neighbour.first} );
            }

    }


    for( int i = 2; i <= n; i++ )
        out<<(( distances[i] < INF ) ? distances[i] : 0)<<" ";

    return 0;
}