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

using namespace std;

const char iname[] = "dijkstra.in";
const char oname[] = "dijkstra.out";
const int  nmax    = 50005;

ifstream fin(iname);
ofstream fout(oname);

int n, m, i, j, k, c, x, y;
vector<pair <int, int> > Gr[nmax];
queue<int> Q;

int D[nmax];
bool viz[nmax];
int cnt[nmax];

struct cmp
{
	bool operator()(const int &a, const int &b)const
	{
		if(D[a] > D[b])
			return 1;
		return 0;
	}
};


void dijkstra()
{	
	for(i = 2; i <= n; i ++)
		D[i] = 287178728;
	Q.push(1);
	viz[1] = 1;
	cnt[1] ++;
	while(!Q.empty())
	{	
		x = Q.front();
		Q.pop();
		if(cnt[x] >= n)
		{
			fout << "Ciclu negativ!";
			exit(0);
		}
		viz[x] = 0;
		for(i = 0; i < Gr[x].size(); i ++)
			if(viz[Gr[x][i].first] == 0)
				if(D[Gr[x][i].first] > D[x] + Gr[x][i].second)
				{
					D[Gr[x][i].first] = D[x] + Gr[x][i].second;
					Q.push(Gr[x][i].first);
					cnt[Gr[x][i].first]++;
					if(cnt[Gr[x][i].first] >= n)
					{
						fout << "Ciclu negativ!";
						exit(0);
					}
				}
	}
}


int main()
{
	fin >> n >> m;
	for(i = 1; i <= m; i ++)
	{
		fin >> x >> y >> c;
		Gr[x].push_back(make_pair(y, c));
	}
	
	dijkstra();
	for(i = 2; i <= n; i ++)
		if(D[i] == 287178728)
			fout << "0 ";
		else
			fout << D[i] << " ";
	return 0;
}