#include<bits/stdc++.h>
using namespace std;
const int N=3e5+10;
int n,m,s,cnt;
long long dis[N];
bool vis[N];
vector<pair<int,int>> G[N];
priority_queue<pair<int,int>,vector<pair<int,int>>,greater<pair<int,int>>> q;
void dijkstra(){
    q.push({0,s});
    while(q.size()){
        int now=q.top().second;
        q.pop();
        if(vis[now]){
            continue;
        }
        vis[now]=1;
        for(auto it:G[now]){
            int x=it.first,y=it.second;
            if(dis[x]>dis[now]+y){
                dis[x]=dis[now]+y;
                q.push({dis[x],x});
            }
        }
    }
    return ;
}
int main(){
    ios::sync_with_stdio(0);cin.tie(nullptr);cout.tie(nullptr);
    cin>>n>>m;
    s=1;
    for(int i=1;i<=n;i++){
        dis[i]=1e18;
    }
    dis[s]=0;
    for(int i=1;i<=m;i++){
        int value,u,v;
        cin>>u>>v>>value;
        G[u].push_back({v,value});
    }
    dijkstra();
    for(int i=1;i<=n;i++){
        if(dis[i]==1e18){
            dis[i]=-1;
        }
        cout<<dis[i]<<" ";
    }
    return 0;
}