#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N = 50010, M = N * 4;
int h[N], nxt[M], w[M], to[M], idx;
void add(int a, int b, int c) {
	to[idx] = b; w[idx] = c;
	nxt[idx] = h[a]; h[a] = idx++;
}
int n, m;
int d[N]; bool vis[N]; int inf = 0x3f3f3f3f;
void spfa() {
	memset(d, 0x3f, sizeof d); queue<int> q; q.push(0); vis[0] = 1, d[0] = 0;
	while(!q.empty()) {
		int u = q.front(); q.pop(); vis[u] = 0;
		for(int i = h[u]; i != -1; i = nxt[i]) {
//			cout << u << ' ' << to[i] << ' ' << w[i] << endl;
			int v = to[i];
			if(d[v] > d[u] + w[i]) {
				d[v] = d[u] + w[i];
				if(vis[v]) continue;
				vis[v] = 1; q.push(v);
			}
		}
	}
	for(int i = 1; i <= n; i++) if(d[i] == inf) {puts("NO"); return ;}
	for(int i = 1; i <= n; i++) printf("%d ", d[i]);
}
#define gc getchar
inline int read() {
	int x = 0, f = 1; char ch = gc();
	while(ch < '0' || ch > '9') {if(ch == '-') f = -f; ch = gc();}
	while(ch >= '0' && ch <= '9') x = x * 10 + (ch ^ 48), ch = gc();
	return x * f;
}
signed main() {
	memset(h, -1, sizeof h); cin >> n >> m;
	for(int i = 1; i <= m; i++) {
		int x = read(), y = read(), z = read();
		add(y, x, z);
	}
	for(int i = 1; i <= n; i++) add(0, i, 0); spfa();
	return 0;
}