#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>
#include <queue>

using namespace std;
#define maxn 50001
#define inf 1 << 30

ifstream f("dijkstra.in");
ofstream g("dijkstra.out");

int n, m, d[maxn], q[maxn];
vector <pair < int, int > > graph[maxn];

void read() {
    f >> n >> m;
    for( int i = 0; i < m; i++ ) {
        int x, y, z;
        f >> x >> y >> z;
        graph[x].push_back( make_pair(y, z) );
    }
}

bool comp( const pair <int, int> & p1, const pair <int, int> & p2 ) {
    if( p1.first < p2.first )
        return true;
        if( p1.first > p2.first ) return false;
        else if( p1.second < p2.second ) return true;
        return false;
}

void dijkstra_heap() {
    int i;
    for( i = 1; i <= n; i++)
        d[i] = inf, q[i] = -1;
    d[1] = 0;
    q[1] = 0;
    int k = 0;
    vector < pair < int, int> > heap; 
    heap.push_back( make_pair( d[1], 1 ) );
    make_heap( heap.begin(), heap.end(), comp );
    k++; // numarul de eleente din heap

    while( k ) {
        int u = heap.front().second;
        k--;
        pop_heap( heap.begin(), heap.end(), comp );
        heap.pop_back();
        int lim = graph[u].size();
        for(int i = 0; i < lim; i++) {
            if( d[u] + graph[u][i].second < d[ graph[u][i].first ] ) {
                 if( q[ graph[u][i].first ] == -1 ) {
                    d[ graph[u][i].first ] = d[u] + graph[u][i].second;
                    heap.push_back( make_pair( d[ graph[u][i].first], graph[u][i].first ) );
                    make_heap( heap.begin(), heap.end(), comp );
                    q[ graph[u][i].first ] ++;
                    k++;
                 }else d[ graph[u][i].first ] = d[u] + graph[u][i].second;
            }
        }   
    }

}

void print_data() {
    for( int i = 2; i <= n; i++ )
        g << d[i] << " ";
}

int main() {
    read();
    dijkstra_heap();
    print_data();
    return 0;
}