#include <stdio.h>
#include <stdlib.h>
#include <values.h>
#define Nmax 50001

struct nod { int a,b; nod * urm; } *g[Nmax], *last[Nmax];
int i, j, *d, n, m, x, y, z;
struct heap { int a,b; } H[Nmax];
int nrH, locH[Nmax];

void dijkstra(int,int*);

inline void swap(heap &x, heap &y)
{
	int temp=locH[x.a];
	locH[x.a]=locH[y.a];
	locH[y.a]=temp;
	heap aux=x;
	x=y;
	y=aux;
}
inline int min(int x, int y) { return x<y?x:y; }

int main()
{
	freopen("dijkstra.in", "r", stdin);
	scanf("%d %d\n", &n, &m);
	d=(int *)calloc(n+3, sizeof(int));
	for (i=1; i<=n; i++) d[i]=-1;
	for (i=1; i<=m; i++)
	{
		scanf("%d %d %d\n", &x, &y, &z);
		nod * q=new nod;
		q->a=y; q->b=z; q->urm=NULL;
		if (g[x]) { last[x]->urm=q; last[x]=q; }
		else { g[x]=q; last[x]=g[x]; }
	}
	dijkstra(1,d);
	freopen("dijkstra.out", "w", stdout);
	for (i=2; i<=n; i++) printf("%d ", d[i]);
	fclose(stdout);
	return 0;
}

void heapUp(int);
void heapDown(int);
void heapExtract();



void dijkstra(int x, int * d)
{

	d[x]=-MAXINT;
	for (nod * p=g[x]; p; p=p->urm)
	{
		H[++nrH].a=p->a; H[nrH].b=p->b; locH[p->a]=nrH; heapUp(nrH);
	}
	while (nrH)
	{
		int x=H[1].a, dist=H[1].b; heapExtract(); d[x]=dist;
		for (nod * p=g[x]; p; p=p->urm)
			if (d[p->a]==-1)
		{
			if (locH[p->a])
			{
				H[locH[p->a]].b=min(H[locH[p->a]].b, dist+p->b ); heapUp(locH[p->a]);
			}
			else
			{
				H[++nrH].a=p->a; H[nrH].b=dist+p->b; locH[p->a]=nrH; heapUp(nrH);
			}
		}
	}
}

void heapUp(int loc)
{
	for (; loc>1 && H[loc].b < H[loc>>1].b; loc>>=1)
	{
		swap(H[loc],H[loc>>1]);
	}
}

void heapDown(int loc)
{
	int loc2;
	while (1)
	{
		loc2=0;
		if ((loc<<1)<=nrH) loc2=loc<<1;
		if (!loc2)
			{ if (((loc<<1)|1)<=nrH) loc2=(loc<<1)|1; }
		else
			{ if ( (loc2|1)<=nrH && H[loc2|1].b<H[loc2].b ) loc2|=1; }
		if (!loc2 || H[loc].b < H[loc2].b) return;
		swap(H[loc],H[loc2]);
		loc=loc2;
	}
}

void heapExtract()
{
	locH[H[1].a]=0;
	swap(H[1],H[nrH--]);
	locH[H[1].a]=1;
	heapDown(1);
}