#include <stdio.h>

const int maxn=50001;
const long inf=0x3f3f3f3f;

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

int n, m;
graf *a[maxn];
int d[maxn], h[maxn], poz[maxn], k;

void add(int where, int what, int cost)
{
    graf *q=new graf;
    q->nod=what;
    q->cost=cost;
    q->next=a[where];
    a[where]=q;
}

void read()
{
    scanf("%d %d", &n, &m);
    int x, y, z;
    for ( int i=1; i<=m; ++i)
    {
        scanf("%d %d %d", &x, &y, &z);
        add(x,y,z);
    }
}

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

void upheap(int what)
{
    int tata;
    while (what>1)
    {
        tata=what>>1;

        if (d[h[tata]]>d[h[what]])
        {
            poz[h[what]]=tata;
            poz[h[tata]]=what;

            swap(tata, what);

            what=tata;
        }
        else
            what=1;
    }
}

void downheap(int what)
{
    int f;
    while (what<=k)
    {
        f=what;
        if ((what<<1)<=k)
        {
            f=what<<1;
            if (f+1<=k)
                if (d[h[f+1]]<d[h[f]])
                    ++f;
        }
        else
            return;

        if (d[h[what]]>d[h[f]])
        {
            poz[h[what]]=f;
            poz[h[f]]=what;
            swap(what,f);
            what=f;
        }
        else
            return;
    }
}

void dijkstra_heap()
{
    for (int i=2; i<=n; ++i)
        d[i]=inf, poz[i]=-1;
    poz[1]=1;
    h[++k]=1;
    while (k)
    {
        int min=h[1];
        swap(1,k);
        poz[h[1]]=1;
        --k;
        downheap(1);
        graf *q = a[min];
        while (q)
        {
            if (d[q->nod]>d[min]+q->cost)
            {
                d[q->nod]=d[min]+q->cost;

                if (poz[q->nod]!=-1)
                    upheap(poz[q->nod]);
                else
                {
                    h[++k]=q->nod;
                    poz[h[k]]=k;
                    upheap(k);
                }
            }
            q=q->next;
        }
    }
}

int main()
{
    freopen("dijkstra.in","r",stdin);
    freopen("dijkstra.out","w",stdout);
    read();
    dijkstra_heap();
    for ( int i=2; i<=n; ++i)
        printf("%d ",d[i]==inf?0:d[i]);
    printf("\n");
    fclose(stdin);
    fclose(stdout);
    return 0;
}