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

using namespace std;

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

int dist[NMAX + 1];

struct edge {
    int node;
    int length;
};
vector <edge> v[NMAX + 1];
int heap[NMAX + 1];
int nodes;
int viz[NMAX + 1];

void init_INF() {
    for ( int i = 0; i <= NMAX; i ++ ) {
        dist[i] = INF + 1;
        heap[i] = INF + 1;
    }
}

void insert_heap( int u ) {
    int poz = nodes;
    heap[nodes++] = u;
    while ( poz > 0 && dist[heap[( poz - 1 ) / 2]] > dist[heap[poz]] ) {
        swap( heap[poz], heap[( poz - 1 ) / 2] );
        poz = ( poz - 1 ) / 2;
    }
}
void erase_heap() {
    int poz = 0;
    swap( heap[0], heap[--nodes] );
    heap[nodes] = INF + 1;
    while ( poz * 2 + 2 < nodes && dist[heap[poz]] > min( dist[heap[poz * 2 + 1]], dist[heap[poz * 2 + 2]] ) ) {
        if ( dist[heap[poz * 2 + 1]] < dist[heap[poz * 2 + 2]] ) {
            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]] > dist[heap[poz * 2 + 1]] )
        swap( heap[poz], heap[poz * 2 + 1] );
}
void vecini( int u ) {
    viz[u] = 1;
    for ( auto& x : v[u] ) {
        dist[x.node] = min( dist[x.node], dist[u] + x.length );
        if ( !viz[x.node] ) {
            insert_heap( x.node );
            viz[x.node] = 1;
        }
    }
    erase_heap();
}
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 } );
    }
    init_INF();
    dist[1] = 0;
    insert_heap( 1 );
    while ( nodes > 0 ) {
        vecini( heap[0] );
    }
    for ( i = 2; i <= n; i ++ ) {
        if ( dist[i] > INF )
            fout << 0 << ' ';
        else
            fout << dist[i] << ' ';
    }
    return 0;
}