#include <bits/stdc++.h>
using namespace std;
#define int long long
const int N = 2e5+5;
const int mod = 998244353;
const int inf = 1e18;
#define fast_io ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define all(x) (x).begin(), (x).end()
int inv(int i) {if (i == 1) return 1; return (mod - ((mod / i) * inv(mod % i)) % mod) % mod;}
int mod_mul(int a, int b) {a = a % mod; b = b % mod; return (((a * b) % mod) + mod) % mod;}
int mod_add(int a, int b) {a = a % mod; b = b % mod; return (((a + b) % mod) + mod) % mod;}
int gcd(int a, int b) { if (b == 0) return a; return gcd(b, a % b);}
int ceil_div(int a, int b) {return a % b == 0 ? a / b : a / b + 1;}
int pwr(int a, int b) {a %= mod; int res = 1; while (b > 0) {if (b & 1) res = res * a % mod; a = a * a % mod; b >>= 1;} return res;}
//////////////////////////// TEMPLATE ////////////////////////////////////
void solve()
{
int n, m;
cin >> n >> m;
vector<pair<int,int>>g[n+1], rev_g[n+1];
for(int i = 0 ; i < m; ++i){
int x, y, wt;
cin >> x >> y >> wt;
g[x].push_back({y,wt});
rev_g[y].push_back({x,wt});
}
// wt, node
multiset<pair<int,int>>s;
vector<int>vis(n+1, 0);
vector<int>dis(n+1, inf);
//dijsktra 1 starts
s.insert({0,1});
dis[1] = 0;
while(!s.empty()){
auto f = *s.begin();
int v_dis = f.first;
int v = f.second;
s.erase(*s.begin());
if(vis[v])continue;
vis[v] = 1;
for(auto child : g[v]){
int child_v = child.first;
int wt = child.second;
if(wt + dis[v] < dis[child_v]){
dis[child_v] = wt + dis[v];
s.insert({dis[child_v],child_v});
}
}
}
for(int i = 0; i <= n; ++i){
vis[i] = 0;
}
for(int i = 1; i <= n; ++i){
s.insert({dis[i],i});
}
while(!s.empty()){
auto f = *s.begin();
int v_dis = f.first;
int v = f.second;
s.erase(*s.begin());
if(vis[v])continue;
vis[v] = 1;
for(auto child : rev_g[v]){
int child_v = child.first;
int wt = child.second;
if(wt + dis[v] < dis[child_v]){
dis[child_v] = wt + dis[v];
s.insert({dis[child_v],child_v});
}
}
}
for(int i = 2; i <= n; ++i){
if(dis[i] == inf){
cout << -1 << " ";
}
else{
cout << dis[i] << " ";
}
}
}
signed main(){
#ifndef ONLINE_JUDGE
freopen("inputF.in", "r", stdin);
freopen("outputF.in", "w", stdout);
#endif
fast_io;
int t = 1;
// cin>>t;
while(t--){
solve();
}
return 0;
}