#include<iostream>
#include<cstring>
#include<vector>
#include<queue>
using namespace std;
struct node
{
	int v,w;
};
vector<node> g[1000000];
queue<int> q;
int cnt[10000000];
int dis[10000000],vis[10000000];
int main()
{
	int n,m;
	cin>>n>>m;
	memset(dis,0x3f,sizeof(dis));
	dis[0]=0;
	q.push(0);
	vis[0]=1;
	for(int i=1;i<=m;i++)
	{
		int u,v,w;
		cin>>u>>v>>w;
		g[v].push_back({u,w});
		g[0].push_back({u,0});
		g[0].push_back({v,0});
	}
	while(q.size())
	{
		int u=q.front();
		q.pop();
		vis[u]=0;
		for(auto it:g[u])
		{
			int v=it.v,w=it.w;
			if(dis[v]>dis[u]+w)
			{
				dis[v]=dis[u]+w;
				cnt[v]=cnt[u]+1;
				if(cnt[v]>n)
				{
					cout<<"NO SOLUTION";
					return 0;
				}
				if(!vis[v])
				{
					vis[v]=1;
					q.push(v);
				}
			}
		}
	}
	int minn=0x3f3f3f3f;
	for(int i=1;i<=n;i++)
		if(minn>dis[i])
			minn=dis[i];
	for(int i=1;i<=n;i++)
		cout<<dis[i]-minn<<endl;
}