#include <bits/stdc++.h>
using namespace std;
const int yhy = 5005;

struct node {
	int u, v, w;
};
node a[yhy];
//priority_queue<int,vector<pair<int,int> >,greater<pair<int,int> > >q;
int dis[yhy], n, m;

bool Bellman_Ford(int s) {
	for (int i = 1; i <= n; i++)
		dis[i] = INT_MAX / 2;
	dis[s] = 0;
	int tiger_king = n;
	while (tiger_king--)
		for (int i = 1; i <= m; i++)
			dis[a[i].v] = min(dis[a[i].v], dis[a[i].u] + a[i].w);
	for (int i = 1; i <= m; i++)
		if (dis[a[i].v] > dis[a[i].u] + a[i].w)
			return false;
	return true;
}

int main() {
	cin >> n >> m;
	for (int i = 1; i <= m; i++)
		cin >> a[i].v >> a[i].u >> a[i].w;
	if (Bellman_Ford(1)) {
		for (int i = 1; i <= n; i++)
			cout << dis[i] << ' ';
		return 0;
	}
	printf("NO");
	return 0;
}