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

#define INT_MAX 2147483647

struct Edge
{
	int v;
	long long weight;
	Edge() : v(), weight() {}
	Edge(int a, int b) : v(a), weight(b) {}
};

struct Vertex
{
	int u;
	std::vector<Edge> myV;
	Vertex() : u(), myV() {}
};

int main()
{
    std::ifstream in("bellmanford.in");
    std::ofstream out("bellmanford.out");
	int nV, nE, a, b, c;
	in >> nV >> nE;
	Vertex *g = new Vertex[nV + 1];
	for(int i = 1; i <= nV; i++)
		g[i].u = i;
	for(int i = 0; i < nE; i++)
	{
		in >> a >> b >> c;
		g[a].myV.push_back(Edge(b, c));
	}
	std::queue<int> myQ;
	long long *d = new long long[nV + 1];
	bool *bC = new bool[nV + 1];
	for(int i = 1; i <= nV; i++)
		d[i] = INT_MAX, bC[i] = false;
	d[1] = 0;
	bC[1] = true;
	myQ.push(1);
	while(!myQ.empty())
	{
		int n = myQ.front();
		myQ.pop();
		bC[n] = false;
		for(unsigned i = 0; i < g[n].myV.size(); i++)
		{
			int m = g[n].myV[i].v;
			long long alt = d[n] + g[n].myV[i].weight;
			if(d[m] > alt)
			{
				d[m] = alt;
				if(!bC[m])
				{
					myQ.push(m);
					bC[m] = true;
				}
			}
		}
	}
	for(int i = 1; i <= nV; i++)
        for(unsigned j = 0; j < g[i].myV.size(); j++)
            if(d[g[i].myV[j].v] > d[i] + g[i].myV[j].weight)
            {
                out << "Ciclu negativ!\n";
                return 0;
            }

	for(int i = 2; i <= nV; i++)
		out << d[i] << ' ';
	return 0;
}