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

#define MN (50001)
#define INF (50000001) // MN*1000+1

int N; // nodes
int M; // edges
int n[MN]; // out degree
int *g[MN]; // graph
int *c[MN]; // cost
int h[MN+1]; // heap, h[0] contains heap size
int d[MN]; // distance
int p[MN]; // position in the heap

void down_heap(int i);
void up_heap(int i);
void dijkstra(int snode);
void pop_heap();
void push_heap(int node);

int main()
{
	int i, A, B, C;

	freopen("dijkstra.in", "r", stdin);
	freopen("dijkstra.out", "w", stdout);

	scanf("%d %d", &N, &M);
	for(i = 0; i < M; ++i) {
		scanf("%d %d %d", &A, &B, &C);
		++n[A-1];
	}
	fclose(stdin);

	for(i = 0; i < N; ++i) {
		//printf("n[%d] = %d\n", i, n[i]);
		g[i] = (int *)malloc((n[i]+1)*sizeof(*g));
		c[i] = (int *)malloc((n[i]+1)*sizeof(*c));
		g[i][0] = 0;
	}

	freopen("dijkstra.in", "r", stdin);
	scanf("%d %d", &N, &M);
	for(i = 0; i < M; ++i) {
		scanf("%d %d %d", &A, &B, &C); --A; --B;
		g[A][++g[A][0]] = B;
		c[A][g[A][0]] = C;
	}

	dijkstra(0);

	for(i = 1; i < N; ++i)
		printf("%d ", d[i] == INF? 0 : d[i]);

	return 0;
}

void dijkstra(int snode)
{
	int i, n1, n2;
	for(i = 0; i < N; ++i) {
		d[i] = INF;
		p[i] = -1;
	}
	h[0] = d[snode] = 0;
	for(push_heap(snode); h[0]; pop_heap()) {
		n1 = h[1];
		//printf("Using d[%d] = %d\n", n1+1, d[n1]);
		for(i = 1; i <= n[n1]; ++i) {
			n2 = g[n1][i];
			if(d[n1]+c[n1][i] < d[n2]) {
				d[n2] = d[n1]+c[n1][i];
				if(p[n2] > 0)
					up_heap(p[n2]);
				else push_heap(n2);
			}
		}
	}
}

void up_heap(int i)
{
	int tmp;
	for(; i > 1 && d[h[i]] < d[h[i/2]]; i /= 2) {
		p[h[i]] = i/2;
		p[h[i/2]] = i;
		tmp = h[i];
		h[i] = h[i/2];
		h[i/2] = tmp;
	}
}

void down_heap(int i)
{
	int j = i, tmp;
	while(1) {
		if(2*i < h[0] && d[h[2*i]] < d[h[i]])
			j = 2*i;
		if(2*i+1 < h[0] && d[h[2*i+1]] < d[h[j]])
			j = 2*i+1;
		if(d[h[j]] < d[h[i]]) {
			p[h[i]] = j;
			p[h[j]] = i;
			tmp = h[i];
			h[i] = h[j];
			h[j] = tmp;
			i = j;
		} else break;
	}
}

void push_heap(int node)
{
	h[++h[0]] = node;
	p[node] = h[0];
	up_heap(h[0]);
}

void pop_heap()
{
	p[h[1]] = -1;
	h[1] = h[h[0]--];
	p[h[1]] = 1;
	down_heap(1);
}