#include <bits/stdc++.h>
#define INFINIT 1000000000

std::vector< std::pair< int, int > > g[50001];
std::priority_queue< std::pair< int, int > > pq;
int d[50001], slct[50001];

int main() {
    FILE *fin, *fout;
    int n, m, i, c, a, b, x, y, dxy;
    fin = fopen( "dijkstra.in", "r" );
    fout = fopen( "dijkstra.out", "w" );
    fscanf( fin, "%d%d", &n, &m );
    for ( i = 0; i < m; i++ ) {
        fscanf( fin, "%d%d%d", &a, &b, &c );
        g[a].push_back( { c, b } );
    }
    for ( i = 1; i <= n; i++ )
        d[i] = INFINIT;
    d[1] = 0;
    pq.push( { -d[1], 1 } );
    while ( !pq.empty() ) {
        while ( !pq.empty() && slct[pq.top().second] ) {
            pq.pop();
        }
        if ( !pq.empty() ) {
            x = pq.top().second;
            dxy = -pq.top().first;
            slct[x] = 1;
            for ( i = 0; i < g[x].size(); i++ ) {
                y = g[x][i].second;
                dxy = g[x][i].first;
                if ( d[x] + dxy < d[y] ) {
                    d[y] = d[x] + dxy;
                    pq.push( { -d[y], y } );
                }
            }
        }
    }
    for ( i = 2; i <= n; i++ )
        fprintf( fout, "%d ", d[i] );
    fclose( fin );
    fclose( fout );
    return 0;
}