#include <stdio.h>

const int nmax=50001;
const int mmax=250001;
const int INF=1050000000;

inline int father(int nod)
{
    return nod/2;
}

inline int ls(int nod)
{
    return nod*2;
}

inline int rs(int nod)
{
    return nod*2+1;
}

int d[nmax];
int H[nmax];
int posH[nmax];

void down(int sz, int pos)
{
    int son,aux;

    do
    {
        son=0;
        if (ls(pos) <= sz)
        {
            son=ls(pos);
            if (rs(pos) <= sz && d[H[rs(pos)]] < d[H[ls(pos)]])
                son=rs(pos);
            if(d[H[son]] >= d[H[pos]])
                son=0;
        }
        if (son)
        {
            aux=posH[H[son]];
            posH[H[son]]=posH[H[pos]];
            posH[H[pos]]=aux;
            aux=H[son];
            H[son]=H[pos];
            H[pos]=aux;
            pos=son;
        }
    }
    while(son);
}

void up(int pos)
{
    int aux;

    while (father(pos) && d[H[father(pos)]] > d[H[pos]])
    {
        aux=posH[H[pos]];
        posH[H[pos]]=posH[H[father(pos)]];
        posH[H[father(pos)]]=aux;
        aux=H[pos];
        H[pos]=H[father(pos)];
        H[father(pos)]=aux;
        pos=father(pos);
    }
}

void in(int &sz, int val)
{
    ++sz;
    H[sz]=val;
    posH[val]=sz;
    up(sz);
}

void out(int &sz, int pos)
{
    posH[H[sz]]=pos;
    posH[H[pos]]=-1;
    H[pos]=H[sz];
    sz--;

    if (father(pos) && d[H[father(pos)]] > d[H[pos]])
        up(pos);
    else
        down(sz,pos);
}

struct element
{
    int nod,cost,next;
};

int head[nmax];
element buff[mmax];

void push(int n2, int n1, int cost, int pos)
{
    buff[pos].nod=n1;
    buff[pos].cost=cost;
    buff[pos].next=head[n2];
    head[n2]=pos;
}

void dijkstra(int n)
{
    int i,sz,c;

    for (i=2; i<=n; i++)
        d[i]=INF;

    sz=0;
    in(sz,1);
    while (sz)
    {
        c=H[1];
        i=head[c];
        out(sz,1);
        while (i)
        {
            if(d[c] + buff[i].cost < d[buff[i].nod])
            {
                d[buff[i].nod]=d[c] + buff[i].cost;
                if (posH[buff[i].nod] == 0)
                    in(sz,buff[i].nod);
                else if (posH[buff[i].nod] != -1)
                    up(posH[buff[i].nod]);
            }
            i=buff[i].next;
        }
    }
}

int main()
{
    FILE *f;
    int n,m,pos,i,a,b,c;

    pos=0;
    f=fopen("dijkstra.in","r");
    fscanf(f,"%d%d",&n,&m);
    for (i=1; i<=m; i++)
    {
        fscanf(f,"%d%d%d",&a,&b,&c);
        ++pos;
        push(a,b,c,pos);
    }
    fclose(f);
    dijkstra(n);
    f=fopen("dijkstra.out","w");
    for (i=2; i<=n; i++)
    {
        if (d[i] == INF)
            fprintf(f,"0 ");
        else
            fprintf(f,"%d ",d[i]);
    }
    fclose(f);
}