#include <stdio.h>

const int nmax=50001;
const int mmax=250001;
const int INF=10e8;

int d[nmax];
int H[nmax];
int pozH[nmax];

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

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

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

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

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

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

inline void up(int pos, int d[])
{
    int c;

    c=H[pos];
    while (father(pos) && d[H[father(pos)]] > d[H[pos]])
    {
        pozH[H[father(pos)]]=pos;
        H[pos]=H[father(pos)];
        pos=father(pos);
    }
    H[pos]=c;
    pozH[c]=pos;
}

inline void down(int pos, int &sz, int d[])
{
    int son, aux;

    do
    {
        son=0;
        if (l_son(pos) <= sz)
        {
            son=l_son(pos);
            if (r_son(pos) <= sz && d[H[r_son(pos)]] < d[H[son]])
                son=r_son(pos);
            if (d[H[son]] > d[H[pos]])
                son=0;
        }
        if (son)
        {
            aux=pos;
            pozH[H[pos]]=pozH[H[son]];
            pozH[H[son]]=aux;
            aux=H[son];
            H[son]=H[pos];
            H[pos]=aux;
            pos=son;
        }
    }
    while (son);
}

void in(int key, int &sz, int d[])
{
    H[++sz]=key;
    pozH[key]=sz;
    up(sz,d);
}

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

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

void dijkstra(int nod, int d[],int n)
{
    int i,sz,c;

    for (i=1; i<=n; i++)
    {
        d[i]=INF;
        pozH[i]=0;
    }
    d[nod]=0;
    //pre[nod]=-1;

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

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

    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);
        push(a,b,c,i);
    }
    fclose(f);
    dijkstra(1,d,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);
}