#include <iostream>
#include <fstream>
#include <vector>

using namespace std;

const int NMAX = 5e4;
const int MMAX = 250000;
const int NIL = -1;

int dist[NMAX + 1];
int reprezentanti[NMAX];


struct node {
    int nod;
    int d;
    int r;
};
struct edges {
    int u;
    int l;
}v[MMAX * 2];
int liste[NMAX + 1];
int list_next[MMAX * 2];
int list_poz;

int rep[NMAX + 1];


node heap[MMAX];
int nodes;

void init() {
    for ( int i = 0; i <= NMAX; i ++ ) {
        dist[i] = -1;
        liste[i] = list_next[i] = NIL;
    }
}

void insert_heap( int u, int d, int r ) {
    int poz = nodes;
    heap[nodes++] = { u, d, r };
    while ( poz > 0 && heap[( poz - 1 ) / 2].d > heap[poz].d ) {
        swap( heap[poz], heap[( poz - 1 ) / 2] );
        poz = ( poz - 1 ) / 2;
    }
}
void erase_heap() {
    int poz = 0;
    swap( heap[0], heap[--nodes] );
    while ( poz * 2 + 2 < nodes && heap[poz].d > min( heap[poz * 2 + 1].d, heap[poz * 2 + 2].d ) ) {
        if ( heap[poz * 2 + 1].d < heap[poz * 2 + 2].d ) {
            swap( heap[poz], heap[poz * 2 + 1] );
            poz = poz * 2 + 1;
        } else {
            swap( heap[poz], heap[poz * 2 + 2] );
            poz = poz * 2 + 2;
        }
    }
    if ( poz * 2 + 1 < nodes && heap[poz].d > heap[poz * 2 + 1].d )
        swap( heap[poz], heap[poz * 2 + 1] );
}

void list_add( int nod1, int nod2, int l ) {
    v[list_poz] = { nod2, l };
    list_next[list_poz] = liste[nod1];
    liste[nod1] = list_poz;
    list_poz ++;
}

void Dijkstra( int r ) {
    int u, d, i, rp;
    for ( i = 0; i < r; i ++ ) {
        insert_heap( reprezentanti[i], 0, reprezentanti[i] );
    }
    while ( nodes > 0 ) {
        u = heap[0].nod;
        d = heap[0].d;
        rp = heap[0].r;
        erase_heap();
        if ( dist[u] == -1 ) {
            dist[u] = d;
            rep[u] = rp;
            i = liste[u];
            while ( i != NIL ) {
                insert_heap( v[i].u, v[i].l + d, rp );
                i = list_next[i];
            }
        }
    }

}
int main() {
    ifstream fin( "dijkstra.in" );
    ofstream fout( "dijkstra.out" );
    int n, m, i, a, b, l, r;
    fin >> n >> m;
    init();
    for( i = 0; i < m; i ++ ) {
        fin >> a >> b >> l;
        list_add( a, b, l );
        ///list_add( b, a, l );
    }
    r = 1;
    reprezentanti[0] = 1;
    Dijkstra( r );
    for ( i = 2; i <= n; i ++ ) {
        fout << dist[i] << ' ';
    }
    return 0;
}