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

using namespace std;

#define nmax 50000
vector<pair<int, int> > graph[nmax];

int n, m;

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

void read_data() {
    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) );
    }
}

void bellmanford() {
    priority_queue <pair <int, int> > heap;
    bool ok = false;
    heap.push( make_pair(0, 1) );
    vector <int> tata( n+1, 0);
    vector <int> distanta( n+1, INT_MAX );
    distanta[1] = 0;

    while( !ok ) {
        ok = true;
        int nod = heap.top().second;
        int dis = heap.top().first * -1;
        heap.pop();
        for( auto x : graph[nod] ) {
            if( distanta[ x.first ] > distanta[nod] + x.second ) {
                distanta[ x.first ] = distanta[nod] + x.second;
            
                tata[x.first] = nod;
                heap.push( make_pair( distanta[x.first] * -1, x.first ) );
                ok = false;
            
            }
        }

    }
    for( int i = 2; i <= n; i++) g << distanta[i] << " ";

}


int main() {
    read_data();
    bellmanford();
}