#include <bits/stdc++.h>
#define M 666013
using namespace std;
ifstream fin("dijkstra.in");
ofstream fout("dijkstra.out");

int n, m, viz[50010], dist[50010], a, b, c, tot;
pair<int, int> now, nxt;
vector< pair<int, int> > v[50010];
priority_queue< pair<int, int>, vector< pair<int, int> >, greater< pair<int, int> > > hip;
int main()
{
    fin >> n >> m;
    for(int i = 1; i <= m; ++i){
        fin >> a >> b >> c;
        v[a].push_back( make_pair(c, b) );
    }
    hip.push( { 0 , 1 } );

    while(!hip.empty()){
        now = hip.top();
        hip.pop();
        if(viz[now.second] == 0){
            viz[now.second] = 1;
            dist[now.second] = now.first;
            for(int i = 0; i < v[now.second].size(); ++i){
                nxt = v[now.second][i];
                hip.push( make_pair(nxt.first + now.first, nxt.second) );
            }
        }
    }

    for(int i = 2; i <= n; ++i)
        fout << dist[i] << ' ';
    return 0;
}