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

int n,m,flag,t = 0x3f3f3f3f;

struct node{
	int nx,w;
};
vector<node> v[N];
int vis[N],dist[N],cnt[N];
void add(int from, int to, int w){
	v[from].push_back({to,w});
}

void spfa(int st){
	memset(dist,0x3f,sizeof(dist));
	deque<int> q;
	q.push_back(st);
	dist[st] = 0;

	while (!q.empty()){
		auto cur = q.front();
		q.pop_front();
		cnt[cur]++;
		if (cnt[cur] >=n) {
			flag = 1;
			printf("NO SOLUTION");
			return;
		}

		for (auto u:v[cur]){

			int nx = u.nx;
			// cout << nx << '\n';
			int w = u.w;
			// cout << dist[nx] << ' '<< dist[cur] << ' ' << w << '\n';
			if (dist[nx] > dist[cur] + w){
				dist[nx] = dist[cur] + w;

				if (!q.empty() && dist[q.front()] > dist[nx] ){
					q.push_front(nx);
				}
				else q.push_back(nx);
			}
		}
	}
}

int main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	cin >> n >> m;
	for (int i = 1; i <= m; i++){
		int x,y,w;
		cin >> x >> y >> w;
		add(y,x,w);
	}

	// superPoint!
	for (int i = 1; i<= n;i++){
		add(0,i,0);
		// add(i,0,0);
	}

	spfa(0);

	if (!flag){
		for (int i = 1; i<= n; i++) t = min(t,dist[i]);
		for (int i = 1; i<= n; i++) printf("%d\n", dist[i] + abs(t));
	}


	return 0;
}