#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define debug(x) cerr << #x << ": " << x << endl;
struct route {
ll dest;
ll length;
};
ll main() {
ll n,m;
cin >> n >> m;
vector<vector<route>> routes (n+1);
ll a, b, c;
for (ll i = 0; i < m; i++)
{
cin >> a >> b >> c;
routes[a].push_back({b,c});
}
// DIJKSTRA ALGORITHM
vector<bool> processed (n+1, false);
vector<ll> distances (n+1, INT_MAX); distances[1] = 0;
priority_queue<pair<ll,ll>,
vector<pair<ll,ll>>,
greater<pair<ll,ll>>> q;
q.push({0,1});
while (q.empty() == false) {
a = q.top().second; q.pop();
if (processed[a]) continue;
processed[a] = true;
for (route& r : routes[a]) {
if (distances[a] + r.length < distances[r.dest]) {
distances[r.dest] = distances[a] + r.length;
q.push({distances[r.dest], r.dest});
}
}
}
for (ll i = 1; i <= n; i++)
{
cout << distances[i] << ' ';
}
cout << endl;
return 0;
}