#include <bits/stdc++.h>
using namespace std;
vector <long long> edge[5000005] , c[5000005];
long long dis[5000005] , vis[5000005];//bool
struct node{
    long long id , d;
    bool operator < (const node& A) const{
        return d > A.d;
    }
};
priority_queue <node> q;
long long n , m , s;
int main(){
    long long u , v , cost;
    cin >> n >> m;
    s = 1;
    while(m--){
        scanf("%d %d %d" , &u , &v , &cost);
        edge[u].push_back(v);
        c[u].push_back(cost);
    }
    for(int i = 1 ; i <= 100001 ; i++) dis[i] = INT_MAX;
    dis[s] = 0;
    q.push((node){s , 0});
    while(!q.empty()){
        node t = q.top();
        q.pop();
        if(vis[t.id] != 0) continue;
        vis[t.id] = 1;
        for(int i = 0 ; i < edge[t.id].size() ; i++){
            long long nu = edge[t.id][i];
            if(vis[nu] == 0 && (dis[t.id] + c[t.id][i]) <  dis[nu]){
                dis[nu] = dis[t.id] + c[t.id][i];
            }
            q.push((node){nu , dis[nu]});
        }
    }
    for(int i = 1 ; i <= n ; i++){
        if(dis[i] != INT_MAX) cout << dis[i] << " ";
        else cout << -1;
    } 
    return 0;
}