#include<algorithm>
using namespace std;

#define DIM 50001
#define INF 1<<30

struct djk{
    int poz,val;};

struct graf{
    int nod,cost;
    graf *urm;};

int n,m,cnt,h[DIM];
djk a[DIM];
graf *lst[DIM];

void add(int nod0,int nod1,int cost){
    graf *p=new graf;

    p->nod=nod1;
    p->cost=cost;
    p->urm=lst[nod0];
    lst[nod0]=p;}

void init(){
    int i;

    for(i=2; i<=n; ++i){
        a[i].val=INF;
        a[i].poz=-1;}}

void swap(int x,int y){
    int aux;

    aux=h[x];
    h[x]=h[y];
    h[y]=aux;}


/*void uph(int k){

    while(k>1&&a[h[k]].val<a[h[fath(k)]].val){
        a[h[k]].poz=fath(k);
        a[h[fath(k)]].poz=k;
        swap(k,fath(k));}}*/

void uph(int k)
{
    int aux;
    while ( k > 1 )
    {
        aux = k >> 1;

        if ( a[ h[aux] ].val > a[ h[k] ].val )
        {
            a[ h[k] ].poz = aux;
            a[ h[aux] ].poz = k;

            swap(aux, k);

            k = aux;
        }
        else
            k = 1;
    }
}

/*void downh(int k){
    int aux;


    while(k<=cnt){
        aux=k;
        if(lson(k)<=cnt){
            aux=lson(k);
            if(aux+1<=cnt&&a[aux+1].val<a[aux].val)
                ++aux;}
        else
            return;
        if(a[h[aux]].val<a[h[k]].val){
            a[h[aux]].poz=k;
            a[h[k]].poz=aux;
            swap(k,aux);
            k=aux;}
        else
            return;}}*/

void downh(int what)
{
    int f;
    while ( what <= cnt )
    {
        f = what;
        if ( (what<<1) <= cnt )
        {
            f = what << 1;
            if ( f + 1 <= cnt )
                if ( a[ h[f + 1] ].val < a[ h[f] ].val )
                    ++f;
        }
        else
            return;

        if ( a[ h[what] ].val > a[ h[f] ].val )
        {
            a[ h[what] ].poz = f;
            a[ h[f] ].poz = what;

            swap(what, f);

            what = f;
        }
        else
            return;
    }
}

void insert(int k){

    h[++cnt]=k;
    a[h[cnt]].poz=cnt;
    uph(cnt);}

void cut(){

	h[1]=h[cnt--];
	a[h[1]].poz=1;
	downh(1);}

void dijkstra(){
	int aux;
	graf *p;

    a[1].poz=1;
    h[++cnt]=1;
	while(cnt){
		aux=h[1];
		cut();
        for(p=lst[aux]; p; p=p->urm)
            if(a[aux].val+p->cost<a[p->nod].val){
                a[p->nod].val=a[aux].val+p->cost;
                if(a[p->nod].poz!=-1)
					uph(a[p->nod].poz);
                else
                    insert(p->nod);}}}

void solve(){
    int i,nod0,nod1,cost;

    scanf("%d%d",&n,&m);
    for(i=0; i<m; ++i){
        scanf("%d%d%d",&nod0,&nod1,&cost);
        add(nod0,nod1,cost);}
    init();
    dijkstra();
    for(i=2; i<=n; ++i)
        if(a[i].val==INF)
            printf("0 ");
        else
            printf("%d ",a[i].val);}

int main(){

    freopen("dijkstra.in","r",stdin);
    freopen("dijkstra.out","w",stdout);

    solve();
    return 0;}