#include <bits/stdc++.h>
#define pb push_back
#define ll long long
#define loop(i,a,b) for(int i=a;i<=b;i++)
#define ln '\n'
#define inf 2e9
#define cin f
#define cout g
using namespace std;
ifstream f("date.in");
ofstream g("date.out");

int n, m, p, x, y, z, d[50001];
bool c[50001];
vector<pair<int, int>> v[50001];

int main()
{
    cin>>n>>m;
    p = 1;
    loop(i,1,m){
        cin>>x>>y>>z;
        v[x].pb({y, z});
    }
    loop(i,1,n)d[i] = inf;
    d[p] = 0;
    priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> q;
    q.push({0, p});
    while(!q.empty()){
        x = q.top().second;
        q.pop();
        if(c[x])continue;
        c[x] = 1;
        for(auto i : v[x]){
            y = i.first;z = i.second;
            if(d[y] > d[x]+z){
                d[y] = d[x]+z;
                q.push({d[y], y});
            }
        }
    }
    loop(i,2,n)cout<<(d[i] == inf ? -1 : d[i])<<' ';

}