#include<bits/stdc++.h>
using namespace std;
queue<int>q;
vector<pair<int,int> >edges[1005];
bool vis[1005];
int cnt[1005],dis[1005];
int main(){
	int n,m;
	cin>>n>>m;
	for(int i=1;i<=m;i++){
		int u,v,w;
		cin>>u>>v>>w;
		edges[v].push_back({u,w});	
	}
	memset(dis,0x7fff,sizeof(dis));
	for(int i=1;i<=n;i++){
		edges[n+1].push_back({i,0});
	}
	dis[n+1]=0;
	cnt[n+1]++;
	q.push(n+1);
	vis[n+1]=1;
	while(!q.empty()){
		int x=q.front();
		q.pop();
		vis[x]=0;
		for(auto y:edges[x]){
			if(dis[y.first]>dis[x]+y.second){
				dis[y.first]=dis[x]+y.second;
				if(!vis[y.first]){
					if(cnt[y.first]>=n){
						cout<<"NO SOLUTION";
						return 0;
					}
					cnt[y.first]++;
					q.push(y.first);
					vis[y.first]=1;
				}
			}	
		}
	}
	int minn=0x7fff;
	for(int i=1;i<=n;i++){
		minn=min(minn,dis[i]);
	} 
	for(int i=1;i<=n;i++)cout<<dis[i]-minn<<'\n';
}