Untitled

#include <bits/stdc++.h>
using namespace std;
#define ll long long

const ll MAXN=1e5+1,INF=1e9;
ll n,m;
vector<pair<ll,ll>> path[MAXN];

void ditcha(ll id){
    vector<unsigned ll> ans(n+1,INF);
    priority_queue<pair<ll,ll>, vector<pair<ll,ll>>, greater<pair<ll,ll>>> q;
    ans[id]=0;
    q.push({0,id});
    while(!q.empty()){
        pair<ll,ll> top=q.top();
        q.pop();
        ll old_ans=top.first,node_id=top.second;
        if(old_ans>ans[node_id])    continue;
        for(auto it:path[node_id]){
            ll cur_nod=it.first,val=it.second;
            if(ans[cur_nod]>ans[node_id]+val){
                ans[cur_nod]=ans[node_id]+val;
                q.push({ans[cur_nod],cur_nod});
            }
        }
    }
    for(ll i=1;i<=n;i++)    cout << ans[i] << " ";
}

int main(){
    ios_base::sync_with_stdio(false);cin.tie(NULL);
    // freopen("TEST.inp","r",stdin);
    // freopen("TEST.out","w",stdout);
    ll a,b,t;
    cin >> n >> m;
    for(ll i=1;i<=m;i++){
        cin >> a >> b >> t;
        path[a].push_back({b,t});
    }
    ditcha(1);
}