#include <bits/stdc++.h>
#define ll long long
#define pb push_back
#define F first
#define S second
#define endl '\n'
#define all(a) (a).begin(),(a).end()
using namespace std;
const ll maxn = 250005;
#define INF 1LL << 61


ifstream fin("dijkstra.in");
ofstream fout("dijkstra.out");

void dijkstra(ll s, const vector<vector<pair<ll,ll>>>& adj , vector<ll> &dist, vector<ll> &pre){
	dist[s]=0;
	priority_queue<pair<ll, ll>, vector<pair<ll, ll>>, greater<pair<ll, ll>>> q;
	q.push({0, s});
	while (!q.empty()) {
		ll u = q.top().S, d = q.top().F;
		q.pop();
		if (d != dist[u]) continue;
		for (auto& edge : adj[u]) {
			ll v = edge.F, w = edge.S;
			if (dist[u] + w < dist[v]) {
				dist[v] = dist[u] + w;
				pre[v] = u;
				q.push({dist[v], v});
			}
		}
	}
}

void solve() {
    ll n, m;
    fin >> n >> m;
    vector<vector<pair<ll, ll>>> adj(maxn, vector<pair<ll, ll>>());
    while (m--) {
        ll x, y, c;
        fin >> x >> y >> c;
        x--;
        y--;
        adj[x].pb({y, c});
    }
    vector<ll> dist(n, maxn), prev(n, -1);
    dijkstra(0, adj, dist, prev);
    for (auto v : dist) {
        if (v == 0) continue;
        if (v == maxn) v = 0; 
        fout << v << " ";
    }
    fout << endl;
}
 
int main() {
    ll t = 1;
//    cin >> t;
    while (t--) {
        solve();
    }
    return 0;
}