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

struct gogu {
    int cost;
    int nod;
    bool operator < ( const gogu & aux ) const {
        return cost > aux.cost;
    }
};

std::vector< gogu >g[50001];
std::priority_queue< gogu >pq;
int d[50001];
char slct[50001];

int main() {
    FILE *fin, *fout;
    int n, m, a, b, c, i, x, y, dxy, dx;
    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( { 0, 1 } );
    while ( !pq.empty() ) {
        while ( !pq.empty() && slct[pq.top().nod] )
            pq.pop();
        if ( !pq.empty() ) {
            x = pq.top().nod;
            dx = pq.top().cost;
            slct[x] = 1;
            pq.pop();
            for ( i = 0; i < g[x].size(); i++ ) {
                y = g[x][i].nod;
                dxy = g[x][i].cost;
                if ( dx + dxy < d[y] ) {
                    d[y] = dx + dxy;
                    pq.push( { d[y], y } );
                }
            }
        }
    }
    for ( i = 2; i <= n; i++ ) {
        if ( d[i] != INFINIT )
            fprintf( fout, "%d ", d[i] );
        else
            fprintf( fout, "0 " );
    }
    fclose( fin );
    fclose( fout );
    return 0;
}