#include <bits/stdc++.h>

using namespace std;
#define pp pair<int, int> 
#define x first
#define y second

const int INF = 0x3f3f3f3f;
const int NMAX = 5e5 + 5;
int n, m;
vector<pp> g[NMAX];

void read() {
	cin >> n >> m;
	for(int i = 0 ; i < m; ++i) {
		int x, y, c;
		cin >> x >> y >> c;
		g[x].push_back({y, c});
	}
}

void solve() {
	
	priority_queue<pp, vector<pp>, greater<pp>> pq;
	
	int dist[NMAX];
	for(int i = 1; i <= n; ++i)
		dist[i] = INF;
	dist[1] = 0;
	pq.push({0, 1});

	while(pq.empty() == false) {

		int node = pq.top().y;
		int d = pq.top().x;
		pq.pop();

		if(dist[node] < d) continue;

		for(pp p : g[node]) 
			if(dist[p.x] > dist[node] + p.y) {
				dist[p.x] = dist[node] + p.y;
				pq.push({dist[p.x], p.x});
			}
	}

	for(int i = 2; i <= n ; ++i) {
		if(dist[i] == INF)
			cout << -1<< '\n';
	else 
			cout << dist[i] << ' ';
	}

	cout << '\n';
}

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

	read();
	solve();

	return 0;
}