#include <fstream>
#include <vector>
#include <queue>

#define N 50005
#define inf (1 << 30)
#define y first
#define c second

using namespace std;

ifstream fin("bellmanford.in");
ofstream fout("bellmanford.out");

int n, m;
typedef pair <int, int> nod;
vector <nod> a[N];
vector <int> d(N, inf), fr(N, 0);;
queue <int> q;

int main()
{
	fin>>n>>m;
	int x, y, c;
	while(m--)
	{
		fin>>x>>y>>c;
		a[x].push_back(nod(y, c));
	}
	
	d[1] = 0;
	q.push(1);
	while(!q.empty())
	{
		x = q.front();
		q.pop();
		
		for(unsigned i=0; i<a[x].size(); i++)
			if(d[x] + a[x][i].c < d[a[x][i].y])
			{
				d[a[x][i].y] = d[x] + a[x][i].c;
				fr[a[x][i].y]++;
				if(fr[a[x][i].y] > n)
				{
					fout<<"Ciclu negativ!";
					return 0;
				}
				
				q.push(a[x][i].y);
			}
	}
	
	for(int i=2 ;i<=n; i++)
		if(d[i] != inf) fout<<d[i]<<' ';
		else fout<<0<<' ';
	
	return 0;
}