#include <fstream>
#include <vector>
#include <set>
#define to first
#define cost second
using namespace std;
const int NMAX = 5e4;
const int MMAX = 25e4;
const int oo = 1e9;
ifstream fin ( "dijkstra.in" );
ofstream fout ( "dijkstra.out" );
vector < pair < int, int > > g[MMAX];
set < pair < int, int > > edges;
int dist[NMAX + 1];
void dijkstra ( int node ) {
    dist[node] = 0;
    edges.insert ( { 0, node } );
    while ( edges.size() ) {
        auto curr = * ( edges.begin () );
        edges.erase ( edges.begin () );
        for ( auto x: g[curr.second] ) {
            if ( dist[curr.second] + x.cost < dist[x.to] ) {
                if ( dist[x.to] != oo )
                    edges.erase( edges.find ( { dist[x.to], x.to } ) );
                dist[x.to] = dist[curr.second] + x.cost;
                edges.insert ( { dist[x.to], x.to } );
            }
        }
    }
}
int main () {
    int n, m, x, y, c;
    fin >> n >> m;
    for ( int i = 1; i <= m; i++ ) {
        fin >> x >> y >> c;
        g[x].push_back ( { y, c } );
    }
    for ( int i = 2; i <= n; i++ )
        dist[i] = oo;
    dijkstra ( 1 );
    for ( int i = 2; i <= n; i++ )
        fout << ( dist[i] == oo? 0 : dist[i] ) << ' ';
    
    return 0;
}