/*
思路：
建一个正向的图，一个反向的图 （分层设图） 
一个点单向相连，最后跑一遍最短路 
*/
#include <bits/stdc++.h>
#define int long long
using namespace std;

const int N = 1e5 + 5;
const int M = 2 * 1e5 + 5;
const long long INF = 0x7f7f7f7f7f7f7f7fll;
struct edge{
	int u, v;long long w;
	int ne;
	edge(){}
	edge(int u1, int v1, long long w1, int net){
		u = u1, v = v1, w = w1, ne = net;
	}
}e[M<<1];
int n, m; 
int head[N<<1], cnt = 0;
void add(int u, int v, long long w){
	e[++cnt] = edge(u, v, w, head[u]);
	head[u] = cnt;
	return;
}
long long dis[N<<1];
bool b[N<<1];
struct node{
	int h;long long w;
	bool operator < (const node n2) const{
		return w > n2.w;
	}
	node(){}
	node(int h1, long long w1){
		h = h1, w = w1;
	}
};
priority_queue<node> q;
void solve(){
	for(int i = 1; i <= n; ++i) add(i, i + n, 0);
	n = n << 1;
//	for(int i = 1; i <= n; ++i){
//		cout << i << "  :";
//		for(int j = head[i]; j; j = e[j].ne){
//			cout << e[j].v << "  ";
//		}
//		cout << '\n';
//	}
//	cout << '\n';
	//dijstra
	for(int i = 1; i <= n; ++i) dis[i] = INF;
	dis[1] = 0;
	
	q.push(node(1, 0));
	for(int i = 1; i <= n; ++i){
		while(!q.empty() && b[q.top().h]) q.pop();
		if(q.empty()) break;
		node now = q.top();
		q.pop();
		b[now.h] = 1;
		dis[now.h] = now.w;
		for(int j = head[now.h]; j; j = e[j].ne){
			int to = e[j].v;
			long long we = e[j].w;
			if(b[to] == 1) continue;
			dis[to] = min(dis[to], dis[now.h] + we);
			q.push(node(to, dis[to]));
		}
	}
//	for(int i = 1; i <= n; ++i){
//		cout << i << ':' << dis[i] << '\n';
//	}
	return;
}
signed main(){
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0); 
	cin >> n >> m;
	for(int i = 1; i <= m; ++i){
		int u, v; long long w;
		cin >> u >> v >> w;
		add(u, v, w);
		add(v + n,u + n, w);
	}
	solve();
	for(int i = n / 2 + 2; i <= n; ++i){
		if(dis[i] == INF) cout << "-1 ";
		else cout << dis[i] << ' ';
	}
	return 0;
}