#include <cstdio>
#include <string.h>
#define DIM 8192
#define N 50001
#define oo 0x3f3f3f3f
#define L ((i)<<1)
#define R ((L)+1)
#define T ((i)>>1)
char ax[DIM];
int  pz;
inline void cit(int &x)
{
            x=0;
            while(ax[pz]<'0' || ax[pz]>'9')
                        if(++pz==DIM)fread(ax,1,DIM,stdin),pz=0;

            while(ax[pz]>='0' && ax[pz]<='9')
            {
                        x=x*10+ax[pz]-'0';
                        if(++pz==DIM)fread(ax,1,DIM,stdin),pz=0;
            }
}
struct nod { int x, cost;nod *n;};
nod *a[N];
int n, m, d[N], H[N], poz[N], nh;
void read()
{

            cit(n);cit(m);
            int p, q, c;
            while(m--)
            {
                        cit(p);cit(q);cit(c);
                        nod *t=new nod;
                        t->x=q;
                        t->cost=c;
                        t->n=a[p];
                        a[p]=t;
            }
}
inline void swap(int i, int j)
{
            int t=H[i]; H[i]=H[j]; H[j]=t;
            poz[H[i]]=i;
            poz[H[j]]=j;
}
inline void upheap(int i)
{
            if(i<=1) return;
            if(d[H[T]] > d[H[i]]) swap(i, T), upheap(T);
}
inline void downheap(int i)
{
            int m=i;

            if(L<=nh)
                        if(d[H[m]] > d[H[L]]) m=L;
            if(R<=nh)
                        if(d[H[m]] > d[H[R]]) m=R;

            if(m!=i) swap(m,i), downheap(m);
}

void dijkstra()
{

            memset(d, oo, sizeof(d));
            d[1]=0;

            int i;
            for(i=1;i<=n;++i) H[i]=i, poz[i]=i;

            for(i=n/2; i; --i) downheap(i);

            nh=n;

            int u;
            nod *it;

            while(nh)
            {
                        u=H[1];
                        swap(1, nh--);
                        downheap(1);

                        for(it=a[u]; it; it=it->n)
                                    if(d[u] + it->cost < d[it->x])
                                    {
                                                d[it->x]=d[u] + it->cost;
                                                upheap(poz[it->x]);
                                    }
            }

            for(i=1;i<=n;++i) if(d[i]==oo) d[i]=0;
            for(i=2;i<=n;++i) printf("%d ", d[i]);


}
int main()
{
            freopen("dijkstra.in","r",stdin);
            freopen("dijkstra.out","w",stdout);
            read();
            dijkstra();
            return 0;
}