#include <stdio.h>
#include <string.h>
#include <stdlib.h>

#define NMAX 50005

typedef struct nod
{
	int vecin;
	long val;
	nod *urm;
} *pnod;

pnod list[NMAX];
int n, m;
int o1, o2;
int nr;


#define DIM 50000

char buf[DIM];
int poz = 0;

int scan()
{
	int x = 0;
	while(buf[poz] < '0' || buf[poz] > '9')
		if(++poz == DIM)
			fread(buf, 1, DIM, stdin);
	while(buf[poz] >= '0' && buf[poz] <= '9')
	{
		x = x*10 + (buf[poz]-'0');
		if(++poz == DIM)
			fread(buf, 1, DIM, stdin);
	}
        return x;
}


inline void baga(int x, int y, long z)
{
	pnod aux;

	aux = new nod;
	aux -> vecin = y;
	aux -> val = z;
	aux -> urm = list[x];

	list[x] = aux;
}


void read()
{
	int x, y;
	long z;
	//scanf("%d %d", &n, &m);
	fread(buf, 1, DIM, stdin);
	n = scan();
	m = scan();
        //printf("%d %d\n", n, m);


	while(m--)
	{
		x = scan();
		y = scan();
		z = scan();
		//printf("%d %d %ld\n", x, y, z);
		//scanf("%d %d %ld", &x, &y, &z);
		baga(x, y, z);
		//baga(y, x, z);
	}
}

#define INFI 0x3f3f3f3f
#define MOD ((2<<16)-1)


void bf()
{
	long inc, sf;
	int c[NMAX*5];  //coada circulara
	long dist[NMAX];
	long cost, next;
	int x, i;
	pnod it;
	char uz[NMAX];

	memset(uz, 0, sizeof(uz));

	memset(dist, INFI, sizeof(dist));

	inc = sf = 1;
	c[1] = 1;
	dist[1] = 0;
	uz[1] = 1;

	while(inc <= sf)
	{
		x = c[ (inc&MOD) ], ++inc;
		//x = c[ inc++];
		uz[x] = 0;

		for(it = list[x]; it != NULL; it = it -> urm)
		{
			next = it -> vecin;
			cost = it -> val;
			if(cost == -1) continue;

			if(dist[next] > dist[x] + cost)
			{
				dist[next] = dist[x] + cost;
				++sf;

				//c[sf] = next;
				if(!uz[next])
				       uz[next] = 1, c[ (sf&MOD) ] = next;
			}
		}
	}
	for(i = 2; i <= n; ++i)
	{
		if(dist[i] != INFI) printf("%ld ", dist[i]);
		else printf("0 ");
	}
}


int main()
{
	int i;
	freopen("dijkstra.in", "r", stdin);
	freopen("dijkstra.out", "w", stdout);

	read();

	bf();


	return 0;
}