#include<fstream>
#include<cstring>
#include<queue>
#include<algorithm>
#include<string.h>
#include<bitset>
#include<ctime>
#include<set>
#include<cmath>
#include<unordered_map>
#include<iomanip>
#include<map>
#include<stack>
#include<vector>
#include<bitset>
#include<functional>
#include<iostream>
#include<deque>
#include<unordered_set>
#include<queue>
#include<list>
#include<array>
#include<ctype.h>
using namespace std;
int n,i,j,ok,m,x,y,c,cost[50500],viz[50500];
bool incoada[50500];
struct muchie
{
	int nod;
	int cost;
}element;
vector<muchie>v[50500];
deque<int>que;
int main()
{
	//ifstream f("file.in");
	//ofstream g("file.out");
	ifstream f("bellmanford.in");
	ofstream g("bellmanford.out");
	f >> n>> m;
	for (i = 1; i <= m; i++)
	{
		f >> x >> y >> c;
		element.nod = y;
		element.cost = c;
		v[x].push_back(element);
	}
	que.push_back(1);
	for (i = 2; i <= n; i++)
		cost[i] = 1 << 30;
	while (que.size() != 0)
	{
		int nod = *que.begin();
		incoada[nod] = 0;
		que.pop_front();
		for (auto it = v[nod].begin(); it != v[nod].end(); it++)
			if(viz[it->nod]==0 || (cost[nod]+it->cost<=cost[it->nod]))
			{
				cost[it->nod] = cost[nod] + it->cost;
				viz[it->nod]++;
				if (incoada[it->nod] == 0)
				{
					incoada[it->nod] = 1;
					que.push_back(it->nod);
				}
				if (viz[it->nod] > n)
				{
					g << "Ciclu negativ!";
					return 0;
				}
			}
	}
	for (i = 2; i <= n; i++)
		g << cost[i] << ' ';
	return 0;
}