#include<stdio.h>
#define Nmax 50002
using namespace std;
int n,m,nh;

struct graf
{
    int v,d;
    graf *adr;
};

struct heap
{
    int v1,v2,d;
};

graf *g[Nmax];//graful
heap h[250002];//heap ordonat dupa distanta
int d[Nmax];//distanta de la nod 1 la toate cele n
int viz[Nmax];//daca am fost la acel nod

void graf_add(int v1,int v2,int d)
{
    graf *p;
    p=new graf;
    p->v=v2;
    p->d=d;
    p->adr=g[v1];
    g[v1]=p;
}

void schimb(int a,int b)//intershimbam 2 val din heap
{
    heap aux;
    aux=h[a];
    h[a]=h[b];
    h[b]=aux;
}

void heap_jos(int x)//mutam o valoare mai jos in heap
{
    int fs,fd,k;
    do
    {
        fs=x<<1;//fiul din stanga
        fd=fs+1;//fiul din dreapta
        k=0;
        if(fs<=nh)//daca ne aflam in heap
        {
            k=fs;
            if(fd<=nh && h[fd].d < h[fs].d)//prioritara este val cea mai mica
                k=fd;
            if(h[k].d >= h[x].d)//daca val aleasa de noi nu este mai mica decat cea curenta
                k=0;
        }
        if(k!=0)
        {
            schimb(x,k);
            x=k;
        }
    }while(k!=0);
}

void heap_sus(int x)//mutam o val in sus in heap
{
    int t;
    t=x>>1;//tatal nodului
    while(x>1 && h[x].d < h[t].d)
    {
        schimb(x,t);
        x=t;
        t=x>>1;
    }
}

void heap_add(int v1,int v2,int d)
{
    ++nh;
    h[nh].v1=v1;
    h[nh].v2=v2;
    h[nh].d=d;
    heap_sus(nh);
}

void heap_sterg()
{
    h[1]=h[nh];
    --nh;
    heap_jos(1);
}

void dijkstra()
{
    int v1,v2,c,i;
    for (i=1;i<=n;i++) d[i]=1000000000;
    d[1]=0;
    graf *p;
    for(p=g[1];p;p=p->adr)
        heap_add(1,p->v,p->d);
    viz[1]=1;
    while(nh!=0)
    {
        v1=h[1].v1;
        v2=h[1].v2;
        c=h[1].d;
        heap_sterg();
        if(viz[v1]==1 && viz[v2]==0)
        {
            d[v2]=c;
            viz[v2]=1;
            for(p=g[v2];p;p=p->adr)
                if(viz[p->v]==0)
                {
                    ++nh;
                    heap_add(v2,p->v,d[v2]+p->d);
                }
        }
    }
}

void citire()
{
    int i,v1,v2,d;
    scanf("%d %d",&n,&m);
    for(i=1;i<=m;++i)
    {
        scanf("%d %d %d",&v1,&v2,&d);
        graf_add(v1,v2,d);
    }
}

void scrie()
{
    int i;
    for(i=2;i<=n;++i)
        printf("%d ",d[i]);
}

int main()
{
    freopen("dijkstra.in","r",stdin);
    freopen("dijkstra.out","w",stdout);
    citire();
    dijkstra();
    scrie();
    fclose(stdin);
    fclose(stdout);
    return 0;
}