#include<fstream>
#include<vector>
using namespace std;
#define maxn 50005
#define inf 1000000000

struct nou{
    int cost,nod;
};

ifstream cin("dijkstra.in");
ofstream cout("dijkstra.out");

int h[maxn],d[maxn],poz[maxn],g[maxn],n,m,k;
vector <nou> v[maxn];

void read(){
    cin>>n>>m;
    int x;
    nou y;
    for(int i=1; i<=m; i++){
        cin>>x>>y.nod>>y.cost;
        v[x].push_back(y);
        g[x]++;
    }
}

void upheap(int what){
    int tata;
    while(what>1){
        tata=what>>1;
        if(d[h[tata]]>d[h[what]]){
            poz[ h[what] ] = tata;
            poz[ h[tata] ] = what;
            swap(h[tata],h[what]);
            what=tata;
        } else what=1;
    }
}

void downheap(int what){
    int f;
    while(what<=k){
        f=what;
        if((what<<1)<=k){
            f=what<<1;
            if(f+1<=k)
                if(d[h[f+1]]<d[h[f]])
                    f++;
        } else return;
        if(d[h[what]]>d[h[f]]){
            poz[h[what]]=f;
            poz[h[f]]=what;
            swap(h[what],h[f]);
            what=f;
        }
        else return;
    }
}

void solve(){
    for(int i=2; i<=n; i++)
        d[i]=inf;
    poz[1]=h[++k]=1;

    while(k){
        int minim=h[1];
        swap(h[1],h[k]);
        poz[h[1]]=1;
        --k;
        int j=0;
        while(j<g[minim]){
            if(d[v[minim][j].nod]>d[minim]+v[minim][j].cost){
                d[v[minim][j].nod]=d[minim]+v[minim][j].cost;

                if(poz[v[minim][j].nod])
                    upheap(poz[v[minim][j].nod]);
                else{
                    h[++k]=v[minim][j].nod;
                    poz[h[k]]=k;
                    upheap(k);
                }
            }
            j++;
        }
    }
    for(int i=2; i<=n; i++)
        if(d[i]==inf)
            cout<<0<<' ';
        else cout<<d[i]<<' ';
}

int main(){
    read();
    solve();
}