#include <iostream>
#include <fstream>
using namespace std;
ifstream fin("dijkstra.in");
ofstream fout("dijkstra.out");
struct arc{
    int x,y,c;
};
arc H[250002];
int nH;
void urcare(int p){
    while(p/2>=1 && H[p/2].c>H[p].c){
        arc aux=H[p];H[p]=H[p/2];H[p/2]=aux;
        p=p/2;
    }
}
void coborare(int p){
    int r;
    while(2*p<=nH){
        r=2*p;
        if(r+1<=nH && H[r+1].c<H[r].c)r++;
        if(H[p].c>H[r].c){
            arc aux=H[p];H[p]=H[r];H[r]=aux;
            p=r;
        }
        else break;
    }
}
int m,start[50002],i,n,vmin,j,k,
    T[3][250002],c,x,y,viz[50002],d[50002],
    tata[50002],infinit=1000000000;
int main()
{
    fin>>n>>m;
    k=0;
    for(i=1;i<=m;i++)
    {
        fin>>x>>y>>c;
        k++;
        T[0][k]=y;  T[1][k]=c;  T[2][k]=start[x];
        start[x]=k;
    }
    for(i=1;i<=n;i++)
    {
        viz[i]=0;
        d[i]=infinit;
    }
    d[1]=0;
    tata[1]=0;
    nH=0;
    viz[1]=1;
    for(j=start[1];j;j=T[2][j]){
        nH++;
        H[nH].x=1;  H[nH].y=T[0][j];    H[nH].c=T[1][j];
        urcare(nH);
    }
    for(i=2;i<=n;i++)
    {
        while(nH>0 && viz[H[1].x]==1 && viz[H[1].y]==1){
            H[1]=H[nH];
            nH--;
            coborare(1);
        }
        if(nH==0)break;
        if(viz[H[1].x]==0){
            k=H[1].x;
            tata[k]=H[1].y;
        }
        else{
            k=H[1].y;
            tata[k]=H[1].x;
        }
        viz[k]=1;
        d[k]=H[1].c;

        for(j=start[k];j!=0;j=T[2][j])
        {
            y=T[0][j];
            c=T[1][j];
            if(viz[y]==0)
            {
                nH++;
                H[nH].x=k;  H[nH].y=y;  H[nH].c=d[k]+c;
                urcare(nH);
            }
        }
    }
    for(i=2;i<=n;i++)
    {
        if(d[i]==infinit)d[i]=0;
        fout<<d[i]<<" ";
    }
    fout.close();
    fin.close();
    return 0;
}