#include <cstdio>
#include <cstdlib>
#include <string>
#define oo 0x3f3f3f3f
#define left(i) ((i)<<1)
#define right(i) (((i)<<1)+1)
#define tata(i) ((i)>>1)
#define maxn 50001

struct nd{ int x, c; nd*n;};

nd *a[maxn];
int n;
int d[maxn];
int poz[maxn];
int H[maxn];
int nh;

void read()
{
    nd *t;
    int m,p,q, c;
    freopen("dijkstra.in","r",stdin);
    scanf("%d %d\n", &n, &m);
    while(m--)
    {
	scanf("%d %d %d\n", &p, &q, &c);
	t=new nd;
	t->x=q;
	t->c=c;
	t->n=a[p];
	a[p]=t;
    }
}

inline void swap(int i,int j)
{
    int tmp=H[i];
    H[i]=H[j];
    H[j]=tmp;
    poz[H[i]]=i;
    poz[H[j]]=j;
}


inline void heapup(int i)
{
    if(i<=1) return ;
    if(d[H[tata(i)]]>d[H[i]]) swap(i, tata(i)),heapup(tata(i));
}


inline void heapdown(int i)
{
    int m=i;
    if(left(i)<=nh)
	if(d[H[left(i)]]<d[H[i]]) m=left(i);
    if(right(i)<=nh)
	if(d[H[right(i)]]<d[H[m]]) m=right(i);
    if(i!=m) swap(i, m), heapdown(m);
}

void solve()
{
    int i;
    nh=n;
    memset(d, oo, sizeof(d));
    d[1]=0;
    for(i=1;i<=n;++i) H[i]=i, poz[i]=i;
    for(i=n/2; i ;--i) heapdown(i);
//    for(i=1;i<=n;++i) heapup(i);
    int u;
    nd *it;

    while(nh)
    {
	u=H[1];
//	H[u]=1;

	swap(1, nh--);
	heapdown(1);

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

    for(i=1;i<=n;++i) if(d[i]==oo) d[i]=0;
    freopen("dijkstra.out","w",stdout);
    for(i=2;i<=n;++i)printf("%d ", d[i]);
    printf("\n");

}


int main()
{
    read();
    solve();
    return 0;
}