#include <bits/stdc++.h>
#define f first
#define s second
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;
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( {c, b} );
    }
    hip.push( {0, 1 } );
    while(!hip.empty()){
        now = hip.top();
        viz[ now.s ] = 1;
        dist[ now.s ] = now.f;
        for(auto nxt : v[now.s])
            if(viz[nxt.s] == 0)
                hip.push( {nxt.f + now.f, nxt.s} );
        while(!hip.empty() && viz[hip.top().s])
            hip.pop();
    }

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