#include <cstdio>
#include <vector>
#include <queue>

#define NMAX 50010
#define INF 250000000

using namespace std;

int n, m;
vector < pair<int, int> > g[NMAX];
int dist[NMAX];
queue <int> q;
bool inq[NMAX];

void read() {
	int i;
	int x, y, z;

	freopen("dijkstra.in", "r", stdin);

	scanf("%d %d", &n, &m);
	for (i=1; i<=m; ++i) {
		scanf("%d %d %d", &x, &y, &z);
		g[x].push_back( make_pair(y,z) );
	}
}

void dijkstra() {
	int i, elem;
	vector < pair<int, int> > :: iterator it;

	for (i=2; i<=n; ++i)
		dist[i] = INF;

	q.push(1);
	while (!q.empty()) {
		elem = q.front();

		for (it=g[elem].begin(); it!=g[elem].end(); ++it)
			if (dist[it -> first] > dist[elem] + it -> second) {
				dist[it -> first] = dist[elem] + it -> second;
				if (inq[it -> first] == 0) {
					q.push(it -> first);
					inq[it -> first] = 1;
				}
			}

		inq[elem] = 0;
		q.pop();
	}
}

void write() {
	int i;

	freopen("dijkstra.out", "w", stdout);

	for (i=2; i<=n; ++i)
		if (dist[i] != INF)
			printf("%d ", dist[i]);
		else
			printf("0 ");
	printf("\n");

}

int main() {
	read();
	dijkstra();
	write();

	return 0;
}