#include <cstdio>
#include <vector>
using namespace std;


long n,m,mn[50005],count,x,y,c;
struct graf{
    long c,nod;
}g2;
vector<graf> g[50005];

struct ab{
    long nod, val;
}heap[250005];

void citire()
{
    scanf("%ld%ld",&n,&m);
    for (int i=1;i<=m;i++)
    {
        scanf("%ld%ld%ld",&x,&y,&c);
        g2.c=c;
        g2.nod=y;
        g[x].push_back(g2);
    }
}

void up(long nod)
{
    ab aux;
    if (heap[nod].val<heap[nod/2].val)
    {
        aux=heap[nod];
        heap[nod]=heap[nod/2];
        heap[nod/2]=aux;
        if (nod/2!=1)
            up(nod/2);
    }
}

void schimba(long a,long b)
{
    ab aux;
    aux=heap[a];
    heap[a]=heap[b];
    heap[b]=aux;
}

void dell(long nod)
{
    if (heap[nod*2].val>heap[nod*2+1].val || nod*2+1>count)
    {
        if (heap[nod*2+1].val<heap[nod].val && nod*2+1<=count)
        {
            schimba(nod,nod*2+1);
            dell(nod*2+1);
        }
        else if (heap[nod*2].val<heap[nod].val && nod*2<=count)
        {
            schimba(nod,nod*2);
            dell(nod*2);
        }
    }
    else if (heap[nod*2].val<=heap[nod*2+1].val)
    {
        if (heap[nod*2].val<heap[nod].val && nod*2<=count)
        {
            schimba(nod,nod*2);
            dell(nod*2);
        }
        else if (heap[nod*2+1].val<heap[nod].val && nod*2+1<=count)
        {
            schimba(nod,nod*2+1);
            dell(nod*2+1);
        }
    }
}

void dijkstra()
{
    long nod;
    ab h;
    while (count>=1)
    {
        nod=heap[1].nod;
        if (mn[nod]==-1)
        {
            mn[nod]=heap[1].val;
            heap[1]=heap[count];
            count--;
            dell(1);
            for (int j=0;j<g[nod].size();j++)
            {
                h.nod=g[nod][j].nod;
                h.val=mn[nod]+g[nod][j].c;
                count++;
                heap[count]=h;
                up(count);
            }
        }
        else
        {
            heap[1]=heap[count];
            count--;
            dell(1);
        }
    }
}
int main()
{
    freopen("dijkstra.in","r",stdin);
    freopen("dijkstra.out","w",stdout);

    citire();
    long nod=1;
    ab h;
    for (int j=0;j<g[nod].size();j++)
    {
        h.nod=g[nod][j].nod;
        h.val=g[nod][j].c;
        count++;
        heap[count]=h;
        up(count);
    }
    for (int i=2;i<=n;i++)
        mn[i]=-1;
    dijkstra();
    for (int i=2;i<=n;i++)
    {
        if (mn[i]==-1)
            mn[i]=0;
        printf("%ld ",mn[i]);
    }


    return 0;
}