#include<iostream>
#include<cstdio>
#include<queue>
#include<cstring>
#include<cmath>
using namespace std;
int n,m;
struct Edge{
	int to,w,nxt;
}edge[5005];
int cnt=0;
int head[5005],dis[5005],vis[5005],count[5005];
void add(int u,int v,int w){
	edge[cnt].to=v;
	edge[cnt].w=w;
	edge[cnt].nxt=head[u];
	head[u]=cnt++;
}
bool spfa(int start){
	queue<int> q;
	memset(dis,0x3f,sizeof(dis));
	dis[start]=0;
	vis[start]=1;
	q.push(start);
	while(!q.empty()){
		int u=q.front();
		q.pop();
		vis[u]=0;
		for(int i=head[u];i!=0;i=edge[i].nxt){
			int v=edge[i].to;
			if(dis[v]>dis[u]+edge[i].w){
				dis[v]=dis[u]+edge[i].w;
				if(!vis[v]){
					vis[v]=1;
					q.push(v);
					count[v]++;
					if(count[v]>n) return false;
				}
			}
		}
	}
	return true;
}
int main(){
	scanf("%d%d",&n,&m);
	for(int i=1;i<=m;i++){
		int u,v,w;
		scanf("%d%d%d",&u,&v,&w);
		add(v,u,w);
	}
	for(int i=1;i<=n;i++) add(0,i,0);
	if(spfa(0)){
		int minn=0x3f;
		for(int i=1;i<=n;i++){
			minn=min(minn,dis[i]);
		}
		minn=abs(minn);
		for(int i=1;i<=n;i++){
			dis[i]+=minn;
			printf("%d\n",dis[i]);
		}
	} 
	else printf("NO SOLUTION\n");
	return 0;
}