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

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});
	}
}

void parcurgere()
{
    Q.push(1);
    while(!Q.empty())
	{
		int NOD = Q.front();
		Q.pop();

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

			if(tmp < costuri[it -> y])
			{
				costuri[it -> y] = tmp;
				viz[it -> y]++;
				if(viz[it -> y] > n)
				{
					negativ = true;
					return;
				}
				Q.push(it -> y);
			}
		}
	}
}

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