#include <iostream>
#include <fstream>
#include <queue>
#include <limits>
#include <vector>
#include <cstring>
#define inf 0x3f3f3f

using namespace std;

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

int n, m;
bool negativ = false;
int viz[50005];

int costuri[50005];

struct edge
{
	int y, cost;
};

queue <int> Q;

vector <edge> graf[50005];

void citire()
{
    for(int i = 1; i <= m; i++)
	{
		int a, b, c;
		in >> a >> b >> c;
        graf[a].push_back({b, c});
	}
}

vector <edge> :: iterator it;
void parcurgere()
{
    Q.push(1);
    while(!Q.empty())
	{
		int NOD = Q.front();
		Q.pop();
		viz[NOD]++;
			if(viz[NOD] > n)
			{
				negativ = true;
				return;
			}

		for(it = graf[NOD].begin(); it != graf[NOD].end(); ++it)
		{
			int tmp = it -> cost + costuri[NOD];

			if(tmp < costuri[it -> y])
			{
				costuri[it -> y] = tmp;
				Q.push(it -> y);
			}
		}
	}
}

int main()
{
    in >> n >> m;
    citire();
    for(int i = 0; i < 50005; i++)
		costuri[i] = inf;
    costuri[1] = 0;
    parcurgere();
    if(negativ == true)
		out << "Ciclu Negativ!";
	else
    for(int i = 2; i <= n; i++)
		out << costuri[i] << " ";
    return 0;
}