#include <cstdio>
#define Nmax 50005
#define inf 1<<30

using namespace std;

FILE *fin=freopen("dijkstra.in","r",stdin);
FILE *fout=freopen("dijkstra.out","w",stdout);

int n,m;

struct nod
{
    int c,x;
    nod *urm;
}*a[Nmax];

int d[Nmax],h[Nmax],p[Nmax],k;

void add(int x, int y, int c)
{
    nod *q = new nod;
    q-> x=y;
    q->c=c;
    q->urm=a[x];
    a[x]=q;
}

void citire()
{
   scanf("%d %d",&n,&m);
   int a,b,c;
   for(int i=0;i<m;i++){
        scanf("%d %d %d",&a,&b,&c);
        add(a,b,c);
   }
}

void swap(int x, int y)
{
    int aux=h[x];
    h[x]=h[y];
    h[y]=aux;
}

void upheap( int w)
{
    int tata;
    while(w>1)
    {
        tata = w>>1;
        if(d[h[tata]]>d[h[w]])
        {
            p[h[w]]=tata;
            p[h[tata]]=w;
            swap(tata,w);
            w=tata;
        }
        else
            w=1;
    }
}

void downheap(int w)
{
    int f;
    while(w<=f)
    {
        f=w;
        if((w<<1)<=k)
        {
            f=w<<1;
            if(f+1<=k)
                if(d[h[f+1]]<d[h[f]])
                    f++;
        }
        else
            return;
        if(d[h[w]]>d[h[f]])
        {
            p[h[w]]=f;
            p[h[f]]=w;
            swap(w,f);
            w=f;
        }
        else
            return;
    }
}

void dijkstra()
{
    for (int i=2;i<=n;i++)
        d[i]=inf,p[i]= -1;
    p[1]=1;
    h[++k]=1;
    while(k)
    {
        int min=h[1];
        swap(1,k);
        p[h[1]]=1;
        --k;
        downheap(1);
        nod *q=a[min];
        while(q)
        {
            if(d[q->x]>d[min]+q->c)
            {
                d[q->x]=d[min]+q->c;
                if(p[q->x]!=-1)
                    upheap(p[q->x]);
                else
                {
                    h[++k]=q->x;
                    p[h[k]]=k;
                    upheap(k);
                }
            }
            q=q->urm;
        }

    }
}

int main()
{
    citire();
    dijkstra();
    for(int i=2;i<=n;i++)
        printf("%d ",d[i]);
    return 0;
}