#include<stdio.h>
const int inf = 1 << 30;

int m,n,d[50010],h[50010],poz[50010],k;

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

graf *a[50010];

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

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("input.in","r",stdin);
    freopen("dijkstra.in","r",stdin);
    freopen("dijkstra.out","w",stdout);
    scanf("%d%d",&n,&m);
    int x,y,z;
    for(int i=1;i<=m;++i)
    {
        scanf("%d%d%d",&x,&y,&z);
        graf *q = new graf;
        q->nod = y;
        q->cost = z;
        q->next = a[x];
        a[x] = q;
    }
    dijkstra_heap();

    for(int i=2;i<=n;++i)
    {
        if(d[i]==inf)
            printf("%d",0);
        else
            printf("%d ",d[i]);
    }
    return 0;
}