#include <bits/stdc++.h>
using namespace std;
const int maxn=3e5;
#define int long long
int sz=0;
pair<int,int> aint[maxn];
void update(int i){
    if(i==1)return;
    if(aint[i/2].second>=aint[i].second){
        return;
    }
    swap(aint[i],aint[i/2]);
    update(i/2);
}
void erasee(){
    aint[1]=aint[sz];
    aint[sz]={0,-10000000000};
    sz--;
    int poz=1;
    while(poz<=sz){
        if(aint[poz].second>=aint[poz*2].second && aint[poz].second>=aint[poz*2+1].second){
            break;
        }
        int indice=2*poz;
        if(aint[indice].second<=aint[indice+1].second)indice++;
        swap(aint[indice],aint[poz]);
        poz=indice;
    }
}
void add(pair<int,int> val){
    sz++;
    aint[sz]=val;
    update(sz);
}
vector<pair<int,int>> v[50001];
int rsp[50001];
signed main()
{
    ifstream cin("dijkstra.in");
    ofstream cout("dijkstra.out");
    int n,m;
    cin>>n>>m;
    for(int i=1;i<=m;i++){
        int l,r,cst;
        cin>>l>>r>>cst;
        v[l].push_back({r,cst});
    }
    for(int i=1;i<=m;i++){
        rsp[i]=1e18;
        aint[i]={0,-100000000000};
    }
    add({1,0});
    //cout<<endl;
    while(sz>0){
        int nod=aint[1].first,val=aint[1].second;
        //cout<<nod<<" "<<val<<endl;
        erasee();
        if(abs(val)>rsp[nod])continue;
        //rsp[nod]=abs(val);
        for(auto i:v[nod]){
            if(rsp[i.first]<abs(val)+i.second)continue;
            rsp[i.first]=abs(val)+i.second;
            //cout<<i.first<<" "<<i.second<<endl<<endl;
            add({i.first,val-i.second});
        }
    }
    for(int i=2;i<=n;i++){
        if(rsp[i]==1e18){
            cout<<0<<" ";
            continue;
        }
        cout<<rsp[i]<<" ";
    }
    /*
    for(int i=1;i<=6;i++){
        int a;
        cin>>a;
        add({0,a});
    }
    cout<<aint[1].second<<endl;
    erasee();
    cout<<aint[1].second<<endl;
    erasee();
    cout<<aint[1].second<<endl;
    erasee();
    cout<<aint[1].second<<endl;
    erasee();
    cout<<aint[1].second<<endl;
    */
    return 0;
}