#include <fstream>
#define NMAX 50000
#define infinit 2000000
using namespace std;
struct heap{
int ind,val;
}h[NMAX+10];
int cnth;
int poz[NMAX+10],s[NMAX+10],d[NMAX+10],t[NMAX+10];
int n,m,i,j;
struct nod{
int vf,lung;
nod* urm;
};
nod* v[NMAX+10];
nod* q;
ifstream f("dijkstra.in");
ofstream g("dijkstra.out");

void up(int p){
    if(p>1&&h[p].val<h[p/2].val){
        swap(h[p],h[p/2]);
        swap(poz[h[p/2].ind],poz[h[p].ind]);
        up(p/2);
    }
}
void down(int p){
    if(2*p<=cnth){
        int x=p;
        if(h[2*p].val<h[x].val)
            x=2*p;
        if(2*p+1<=cnth&&h[2*p+1].val<h[x].val)
            x=2*p+1;
        if(x!=p){
            swap(h[p],h[x]);
            swap(poz[h[p].ind],poz[h[x].ind]);
            down(x);
        }
    }
}

void adaug(int a){
    h[++cnth].val=a;
    h[cnth].ind=q->vf;
    poz[q->vf]=cnth;
    up(cnth);
}
void scot(int a){
    h[poz[a]]=h[cnth];
    poz[h[cnth].ind]=poz[a];
    cnth--;
    up(poz[a]);
    down(poz[a]);
}
int main()
{
    f>>n>>m;
    for(i=1;i<=m;i++){
        int a,b,c;
        f>>a>>b>>c;
        nod* q=new nod;
        q->vf=b;
        q->lung=c;
        q->urm=v[a];
        v[a]=q;
    }

 //   t[1]=-1;
    for(i=2;i<=n;i++)
        d[i]=infinit;

    s[1]=1;
    for(i=1;i<n;i++){
        int x;
        if(i==1)    x=1;
        else{
            x=h[1].ind;
            s[x]=1;
            scot(1);
        }
        for(q=v[x];q;q=q->urm)
        if(s[q->vf]==0&&d[x]+q->lung<d[q->vf]){
            if(d[q->vf]==infinit)
                adaug(d[x]+q->lung);
            else{
                scot(q->vf);
                adaug(d[x]+q->lung);
            }
            d[q->vf]=d[x]+q->lung;
          //  t[q->vf]=x;
        }
    }
    for(i=2;i<=n;i++)
        g<<d[i]<<" ";
    return 0;
}