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


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

struct muchie{
    long x,y,c;
}v[250005];

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

void citire()
{
    scanf("%ld%ld",&n,&m);
    for (int i=1;i<=m;i++)
    {
        scanf("%ld%ld%ld",&v[i].x,&v[i].y,&v[i].c);
        g2.c=v[i].c;
        g2.nod=v[i].y;
        g[v[i].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)
    {
        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+1);
        }
    }
    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+1);
        }
        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;
    vector<ab> wait;
    while (count>=1)
    {
        for (int j=0;j<g[heap[1].nod].size();j++)
        {
            nod=g[heap[1].nod][j].nod;
            if (mn[nod]==-1 || mn[nod]>heap[1].val+g[heap[1].nod][j].c)
            {
                mn[nod]=heap[1].val+g[heap[1].nod][j].c;
                count++;
                h.nod=nod;
                h.val=mn[nod];
                wait.push_back(h);
            }
        }
        heap[1]=heap[count];
        count--;
        dell(1);
        for (int i=0;i<wait.size();i++)
        {
            count++;
            heap[count]=wait[i];
            up(count);
        }
        wait.clear();
    }
}
int main()
{
    freopen("dijkstra.in","r",stdin);
    freopen("dijkstra.out","w",stdout);

    citire();
    heap[1].nod=1;
    count++;
    for (int i=2;i<=n;i++)
        mn[i]=-1;
    dijkstra();
    for (int i=2;i<=n;i++)
        printf("%ld ",mn[i]);

    return 0;
}