#include<fstream>
#include<vector>
#include<queue>
#include<algorithm>
using namespace std;


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

struct Node
{
	int x, c;
};

vector<Node> G[50001];
queue<int> Q;
int N, M;
int D[50001],i,j,a,b,c;
int E[50001];
bool V[50001];
int main()
{
	in >> N >> M;
	Node q;
	for (i = 1;i <= M;++i)
	{
		in >> a >> b >> c;
		q.x = b;
		q.c = c;
		G[a].push_back(q);
	}
	
	int ciclu_neg = 0;
	for (i = 1;i <= N;++i)
		D[i] = (1 << 30);
	D[1] = 0;
	V[1] = 1;
	Q.push(1);
	int el;
	while (Q.size() && !ciclu_neg)
	{
		el = Q.front();
		Q.pop();
		V[el] = 0;
		for (i = 0;i < G[el].size();++i)
		{
			if (D[el] + G[el][i].c < D[G[el][i].x])
			{
				D[G[el][i].x] = D[el] + G[el][i].c;
				if (!V[G[el][i].x])
				{
					if (E[G[el][i].x] > N)
					{
						ciclu_neg = 1;
					}
					else
					{
						V[G[el][i].x] = 1;
						Q.push(G[el][i].x);
						++E[G[el][i].x];
					}
				}
			}
		}
	}


   if(!ciclu_neg)
	 for (i = 2;i <= N;++i)
		out << D[i] << " ";
   else
   {
	   out << "Ciclu negativ!";
   }

	return 0;
}