#include <cstdio>
#include <vector>
using namespace std;

#define MAXN 50000
#define MAM 250000
#define INFINIT 999999999

struct edge {
    int node;
    short int cost;
};

vector <edge> G[MAXN+1];
int dist[MAXN+1];

inline int left_son( int x ) {
    return x<<1;
}

inline int right_son( int x ) {
    return (x<<1) + 1;
}

inline int father( int x ) {
    return x >> 1;
}

int heap[MAXN+1];
bool removed[MAXN+1];
int heap_len;

void sift( int nod ) {
    int son = 1;
    do {
        son = 0;
        if( left_son( nod ) <= heap_len )
            son = left_son( nod );
        if( right_son( nod ) <= heap_len && dist[heap[right_son(nod)]] < dist[heap[nod]] )
            son = right_son( nod );

        if( dist[heap[son]] >= dist[heap[nod]] )
            son = 0;

        if( son ) {
            int aux = heap[nod];
            heap[nod] = heap[son];
            heap[son] = aux;
        }
    }while( son );
}

void percolate( int nod ) {
    int key = heap[nod];

    while( nod > 1 && dist[key] < dist[heap[father(nod)]] ) {
        heap[nod] = heap[father(nod)];
        nod = father(nod);
    }

    heap[nod] = key;
}

void add( int nod ) {
    heap[++heap_len] = nod;
    percolate( heap_len );
}

void cut( int nod ) {
    removed[heap[nod]] = true;
    heap[nod] = heap[heap_len];
    --heap_len;

    if( nod > 1 && dist[heap[nod]] < dist[heap[father(nod)]] )
        percolate( nod );
    else
        sift( nod );
}

int main () {
    FILE *f, *g;
    f = fopen( "dijkstra.in", "r" );
    g = fopen( "dijkstra.out", "w" );

    int n, m, a, b, c;

    fscanf( f, "%d%d", &n, &m );

    edge x;
    for( int i = 0 ; i < m ; ++i ) {
        fscanf( f, "%d%d%d", &a, &b, &c );
        x.node = b;
        x.cost = c;
        G[a].push_back(x);
    }

    add( 1 );

    for( int i = 2 ; i <= n ; ++i )
        dist[i] = INFINIT;

    while( heap_len ) {
        int nod = heap[1];
        cut( 1 );

        for( int i = 0 ; i < G[nod].size() ; ++i )
            if( !removed[G[nod][i].node] ) {
                int D = dist[nod] + G[nod][i].cost;
                if( D < dist[G[nod][i].node] ) {
                    dist[G[nod][i].node] = D;
                    add( G[nod][i].node );
                }
            }
    }

    for( int i = 2 ; i <= n ; ++i ) {
        if( dist[i] == INFINIT )
            dist[i] = 0;
        fprintf( g, "%d ", dist[i] );
    }

    fclose( f );
    fclose( g );
    return 0;
}