九敏

#include <bits/stdc++.h>
using namespace std;
#define int long long
const int inf = 0x3f3f3f3f3f3f3f3;
const int N = 3e5 + 10;
int n, m, dis[N];
struct Point { int u, v, w; }a[N];
struct edge{int to, nxt, w;}e[N];

int h[N], cnt;
bool vis[N];
queue<int> q;

inline void add (int u, int v, int w){
	e[++cnt].to = v;
	e[cnt].w = w;
	e[cnt].nxt = h[u];
	h[u] = cnt;
	// e[++cnt] = {v, h[u], w}, h[u] = cnt;
}
inline void Dijkstra (int s){
	memset (dis, 0x3f, sizeof(dis));
	dis[s] = 0; vis[s] = 1;
	q.push (s);
	while (!q.empty()){
		int u = q.front (); q.pop();
		for (int i=h[u]; i; i=e[i].nxt){
			int v = e[i].to, w = e[i].w;
			if (dis[v] > dis[u] + w) dis[v] = dis[u] + w;
			if (!vis[v]){
				q.push(v); vis[v] = 1;
			}
		}
	}
}
signed main (){
	scanf ("%lld%lld", &n, &m);
	for (int i=1, u, v, w; i<=m; i++){
		scanf ("%lld%lld%lld", &u, &v, &w);
		add (u, v, w);
	}
	Dijkstra(1);
	for (int i=1; i<=n; i++){
		if (dis[i] == inf) printf ("-1 ");
		else printf ("%lld ", dis[i]); 
	}
    return 0;
}