#include <bits/stdc++.h>
	
#define ff first
	
#define ss second
	
 
	
using namespace std;
	
typedef long long ll;
	
typedef long double ld;
	
typedef pair<int, int> pi;
	
typedef pair<ll, ll> pll;
	
typedef pair<ld, ld> pld;
	
typedef vector<int> vi;
	
typedef vector< vector<int> > vvi;
	
 
	
const string file = "bellmanford";
	
const ll INF = 9223372036854775807ll;
	
const int dx[] = {1, -1, 0, 0}, dy[] = {0, 0, 1, -1}, inf = 2147483647;
	
 
	
int n, m;
	
vector< vector<pi> > graph;
	
vi dist;
	
 
	
signed main()
	
{
	
    ifstream fin (file+".in");
	
    ofstream fout (file+".out");
	
    fin >> n >> m;
	
    graph.resize(n);
	
    dist.resize(n, inf);
	
    vector<bool> ok(n, false);
	
    for (int i = 0; i < m; ++i){
	
        int a, b, c;
	
        fin >> a >> b >> c;
	
        --a, --b;
	
        graph[a].push_back(make_pair(b, c));
	
    }
	
    priority_queue<int, vector<pi>, greater<pi> > q;
	
    dist[0] = 0;
	
    q.push(make_pair(0, 0));
	
    while(!q.empty()){
	
        int nod = q.top().ss;
	
        q.pop();
	
        ok[nod] = true;
	
        for (auto neighbor : graph[nod])
	
            if (dist[nod]+neighbor.ss < dist[neighbor.ff]){
	
                dist[neighbor.ff] = dist[nod]+neighbor.ss;
	
                q.push(make_pair(dist[neighbor.ff], neighbor.ff));
	
            }
	
    }
	
    for (int i = 1; i < n; ++i)
	
        fout << (dist[i] == inf ? 0 : dist[i]) << " ";
	
    return 0;
	
}