#include<fstream>
#include<queue>
#define maxint 99999999
using namespace std;
ifstream fin("ExamStat.in");
ofstream fout("ExamStat.out");
int n[1001][1001],c[1001]={0};
int dist[1001];
bool used[1001]={0};
int N,M;
queue<int> q;
bool SPFA(int x)
{
    int i;
	for(i=1;i<=N;i++) dist[i]=maxint;
	dist[x]=0;
    q.push(x);//将该点入队
    used[x]=1;//设置其为已访问
	c[x]=1;
    while(!q.empty())
    {
        int cur=q.front();
        q.pop();//出队
        for(i=1;i<=N;i++)
		{
            if(dist[i]>dist[cur]+n[cur][i])
            {
                dist[i]=dist[cur]+n[cur][i];
                if(!used[i])
                {
                    used[i]=1;
					c[i]++;
                    q.push(i);
					if(c[i]>N) return 0;
					
                }
            }
		}
        used[cur]=0;
    }
    return 1;
}
int main()
{
	fin>>N>>M;
	int a,b,c;
	for(int i=1;i<=N;i++) for(int j=1;j<=N;j++) n[i][j]=maxint;
	for(int i=1;i<=N;i++) n[i][i]=0;
	for(int i=1;i<=M;i++)
	{
		fin>>a>>b>>c;
		n[a][b]=c;
	}
	if(!SPFA(1))
	{
		fout<<"SOMEONE LAY!"<<endl;
		return 0;
	}
	int maxn=0-maxint,p=-1;
	for(int i=1;i<=N;i++)
	{
		if(maxn<dist[i])
		{
			maxn=dist[i];
			p=i;
		}
	}
	SPFA(p);
	for(int i=1;i<=N;i++) 
	{
		if(dist[i]!=maxint) fout<<0-dist[i]<<" ";
		else fout<<"-1 ";
	}
	fout<<endl;
	return 0;
}