#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<string>
#include<cstring>
#include<iomanip>
#include<vector>
#include<set>
#define IOS ios_base::sync_with_stdio(0); cin.tie(0);

using namespace std;

#define inf 0x3f3f3f3f
#define int long long
#define endl '\n'

const int maxn = 300010;

struct node {
	int v, w;
	node(){}
	node(int vv, int ww) {
		v = vv;
		w = ww;
	}
};

int n, m;
vector<node> g[maxn];
bool vis[maxn];
int d[maxn];
set<pair<int, int> >minHeap;

signed main() {
	IOS;
	cin >> n >> m;
	for (int i = 1;i <= m;i++) {
		int u, v, w;
		cin >> u >> v >> w;
		g[u].push_back(node(v, w));
	}

	memset(d, 0x3f, sizeof(d));
	d[1] = 0;

	minHeap.insert(make_pair(0, 1));
	while (!minHeap.empty()) {
		int mind = minHeap.begin()->first;
		int v = minHeap.begin()->second;
		minHeap.erase(minHeap.begin());
		if (mind >= inf) {
			break;
		}
		for (int i = 0;i < g[v].size();i++) {
			if (d[g[v][i].v] > d[v] + g[v][i].w) {
				minHeap.erase(make_pair(d[g[v][i].v], g[v][i].v));
				d[g[v][i].v] = d[v] + g[v][i].w;
				minHeap.insert(make_pair(d[g[v][i].v], g[v][i].v));
			}
		}
	}

	for (int i = 1;i <= n;i++) {
		if (d[i] >= inf) cout << -1 << ' ';
		else cout << d[i] << ' ';
	}
	cout << endl;
	return 0;
}

//Fununugugu Code

#1, #7, #8 都炸了，不知道为啥输出了个负号（