#include<fstream>
#include<vector>
#define NMAX 50002
#define Inf 200000000
using namespace std;
ifstream fin("bellmanford.in");
ofstream fout("bellmanford.out");
int n,m,i,x,y,d[NMAX],c[300000],j,sel[NMAX];
vector<int>A[NMAX];
vector<int>cost[NMAX];
int main()
{
	fin>>n>>m;
	for (i=1;i<=n;i++)
		d[i]=Inf;
	d[1]=0;
	for (i=1;i<=m;i++)
	{
		fin>>x>>y>>j;
		cost[x].push_back(j);
		A[x].push_back(y);
	}
	int ic,sc,z;
	ic=sc=1; c[ic]=1;
		while (ic<=sc)
			{
				z=c[ic];
				for (y=0;y<A[z].size();y++)
					if (d[z]+cost[z][y]<d[A[z][y]])
					{
						d[A[z][y]]=d[z]+cost[z][y];
						c[++sc]=A[z][y];
						sel[A[z][y]]++;
						if (sel[A[z][y]]==n)
						{
							
							fout<<"Ciclu negativ!";
							fout.close(); return 0;
						}
					}
				ic++;
			}
		for (i=2;i<=n;i++)
			fout<<d[i]<<' ';
fout.close();
return 0;}