#include <bits/stdc++.h>
using namespace std;
const int cal = 5005;
struct node{
	int u,v,w;
};
node a[cal];
long long zzh[cal],n,m;
bool jj(int s){
	for (int i=1;i<=n;i++) zzh[i]=2147483647/2;
	zzh[s]=0;
	int jj=n;
	while (jj--)
		for (int i=1;i<=m;i++)
			zzh[a[i].v]=min(zzh[a[i].v],zzh[a[i].u]+a[i].w);
	for (int i=1;i<=m;i++)
		if (zzh[a[i].v]>zzh[a[i].u]+a[i].w)
			return false;
	return true;
}
int main(){
	long long minn=2147483647;
	cin>>n>>m;
	for(int i=1;i<=m;i++) cin>>a[i].v>>a[i].u>>a[i].w;
	if(jj(1)){
		for (int i=1;i<=n;i++){
			if(zzh[i]<=minn) minn=zzh[i];
		}
		for (int i=1;i<=n;i++) zzh[i]=zzh[i]-minn;
		for (int i=1;i<=n;i++) cout<<zzh[i]<<endl;
		return 0;
	}
	cout<<"NO SOLUTION";
	return 0;
}