#include <fstream>
#include <vector>
using namespace std;

ifstream cin("dijkstra.in");
ofstream cout("dijkstra.out");
#define int long long

pair<int,int> h[1000001];
vector<pair<int,int>> v[50001];
int min1[50001],n,m;

int tata(int nod){
    return nod/2;
}

int fiu_st(int nod){
    return 2*nod;
}
int fiu_dr(int nod){
    return 2*nod+1;
}
void shift(int n,int k){
    int fiu;
    do{
        fiu=0;
        if(fiu_st(k)<=n){
            fiu=fiu_st(k);
            if(fiu_dr(k)<=n && h[fiu_dr(k)]>h[fiu_st(k)]) fiu=fiu_dr(k);
            if(h[fiu]<=h[k]) fiu=0;
        }
        if(fiu){
            swap(h[k],h[fiu]);k=fiu;
        }
    }while(fiu);
}

void percolate(int n,int k){
    pair<int,int> key=h[k];
    while(k>1 && key>h[tata(k)]){
        h[k]=h[tata(k)];k=tata(k);
    }
    h[k]=key;
}

void cut(int &n,int k){
    h[k]=h[n];n--;
    if(k>1 && h[k]>h[tata(k)])
        percolate(n,k);
    else shift(n,k);
}

void insert(int &n,int k,int k1){
    n++;
    h[n]={k,k1};
    percolate(n,n);
}
void dij(int poz){
    int i,cnt=1,nod,minc,poz1=0;
    for(i=1;i<=n;i++){
        min1[i]=(long long)1e18;
        if(i!=poz) insert(poz1,(long long)-1e18,i);
    }
    min1[poz]=0;insert(poz1,0,poz);
    while(poz1){

        auto it=h[1];cut(poz1,1);
        nod=it.second;minc=-it.first;
        ///printf("%d %d\n",nod,minc);
        for(auto it:v[nod]){
            if(min1[it.first]>minc+it.second){
                min1[it.first]=minc+it.second;
                insert(poz1,-min1[it.first],it.first);
            }
        }
    }
    for(i=2;i<=n;i++){
        if(min1[i]==1e18) cout<<"0 ";
        else cout<<min1[i]<<" ";
    }
}
signed main()
{
    ios_base::sync_with_stdio(false);cin.tie(NULL);
    int i,a,b,c;
    cin>>n>>m;
    for(i=1;i<=m;i++){
        cin>>a>>b>>c;
        v[a].push_back({b,c});
    }
    dij(1);
    return 0;
}