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

using namespace std;

const int INF = 1e9 + 1;
const int NMAX = 5e4;

int dist[NMAX + 1];

struct node {
    int nod;
    int d;
};
struct edge {
    int u;
    int l;
};
vector <edge> v[NMAX + 1];
node heap[NMAX + 1];
int nodes;

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

void insert_heap( int u, int d ) {
    int poz = nodes;
    heap[nodes++] = { u, d };
    while ( poz > 0 && dist[heap[( poz - 1 ) / 2].nod] > dist[heap[poz].nod] ) {
        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 && dist[heap[poz].nod] > min( dist[heap[poz * 2 + 1].nod], dist[heap[poz * 2 + 2].nod] ) ) {
        if ( dist[heap[poz * 2 + 1].nod] < dist[heap[poz * 2 + 2].nod] ) {
            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 && dist[heap[poz].nod] > dist[heap[poz * 2 + 1].nod] )
        swap( heap[poz], heap[poz * 2 + 1] );
}

void Dijkstra() {
    int u, d;
    init();
    insert_heap( 1, 0 );
    while ( nodes > 0 ) {
        u = heap[0].nod;
        d = heap[0].d;
        erase_heap();
        if ( dist[u] == -1 ) {
            dist[u] = d;
            for ( auto& x : v[u] ) {
                insert_heap( x.u, x.l + d );
            }
        }
    }

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