#include<queue>
#include<cstdio>
#include<vector>
using namespace std;

#define INFINIT 999999999

typedef vector<int> VI;

struct muchie {
	int c, t;
}a;

VI d;
vector<muchie> c[50000];
int n, m;

struct cmp {
	bool operator()(int i, int j) {
		return d[i] < d[j];
	}
};

priority_queue<int, VI, cmp> heap;

void dijkstra(int sursa) {
	int k;
	vector<muchie>::iterator it;
	d.assign(n + 1, INFINIT);
	d[sursa] = 0;
	heap.push(sursa);
	while( !heap.empty() ) {
		k = heap.top();
		heap.pop();
		for(it = c[k].begin(); it != c[k].end(); ++it)
			if(d[(*it).t] > d[k] + (*it).c) {
				d[(*it).t] = d[k] + (*it).c;
				heap.push((*it).t);
			}
	}
}

int main() {
	int i, m1, m2, cost;
	freopen("dijkstra.in", "r", stdin);
	freopen("dijkstra.out", "w", stdout);
	scanf("%d%d", &n, &m);
	while(m--) {
		scanf("%d%d%d", &m1, &m2, &cost);
		a.t = m2; a.c = cost;
		c[m1].push_back(a);
	}
	dijkstra(1);
	for(i = 2; i <= n; ++i) {
		if(d[i] == INFINIT)
			printf("0");
		else printf("%d", d[i]);
		if(i != n)
			printf(" ");
	}
	printf("\n");
	return 0;
}