#include <fstream>
#define NMAX 50010
#define infinit 20000000
using namespace std;
ifstream f("dijkstra.in");
ofstream g("dijkstra.out");
struct nod{
    int vf,lung;
    nod *urm;
};
nod *v[NMAX];
nod *q;
int poz[NMAX],s[NMAX],d[NMAX],n,m,i,j;
struct heap{
int ind,val;
}h[NMAX];
int cnth;
void up(int p){
    if(p>1&&h[p].val<=h[p/2].val){
        swap(h[p],h[p/2]);
        swap(poz[h[p].ind],poz[h[p/2].ind]);
        up(p/2);
    }
}
void down(int p){
    if(2*p<=cnth){
        int x=p;
        if(h[2*p].val<=h[p].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[x],h[p]);
            swap(poz[h[x].ind],poz[h[p].ind]);
            down(x);
        }
    }
}

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

    for(i=2;i<=n;i++)
        d[i]=infinit;

    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;
            }
        }

    }
    for(i=2;i<=n;i++)
        if(d[i]==infinit)
            g<<"0 ";
        else
            g<<d[i]<<" ";

    return 0;
}