#include <iostream>
#include <cstdio>
#include <fstream>
#include <set>
#include <vector>
#include <list>
#include <queue>
#include <algorithm>
#include <stack>

#define vertex first
#define cost second
#define inf 10000000

using namespace std;

int n, m, k, dist[1000], pre[1000];

class comparator {
public:
	bool operator()(const pair<int, int>& l, const pair<int, int>& r) {
		return l.cost > r.cost;
	}
};

priority_queue<pair<int, int>, vector<pair<int, int> >, comparator > pq;
vector<vector<pair<int, int> > > graph;
bool visited[1000];

int main()
{
	int i, j, a, b, c, u, v;
	freopen("dijkstra.in", "r", stdin);
	freopen("dijkstra.out", "w", stdout);
	scanf("%d %d", &n, &m);
	graph.resize(n);
	k = 1;
	for (i = 1; i <= m; i++) scanf("%d%d%d", &a, &b, &c), graph[a - 1].push_back(make_pair(b - 1, c));//graph[b-1].push_back(make_pair(a-1, c));
	for (i = 0; i < n; i++) dist[i] = inf;
	dist[k - 1] = 0;
	pre[k - 1] = k - 1;
	pq.push(make_pair(k - 1, 0));
	while (!pq.empty()) {
		u = pq.top().vertex;
		pq.pop();
		if (visited[u]) continue;
		visited[u] = true;
		for (pair<int, int> vecin : graph[u]) {
			if (!visited[vecin.vertex] && dist[vecin.vertex] > dist[u] + vecin.cost) {
				pq.push(make_pair(vecin.vertex, dist[u] + vecin.cost));
				dist[vecin.vertex] = dist[u] + vecin.cost;
				pre[vecin.vertex] = u;
			}
		}
	}
	for (i = 1; i < n; i++)printf("%d ", dist[i] != inf ? dist[i] : -1);

	return 0;
}