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

using namespace std;

const int cmax = INT_MAX;
const int dmax = INT_MAX;
//ifstream f("apm.in");
//ofstream o("apm.out");
//ifstream f("dijkstra.in");
//ofstream o("dijkstra.out");
ifstream f("bellmanford.in");
ofstream o("bellmanford.out");
class Graph
{
	vector<vector<int>> adjList;
	vector<vector<pair<int, int>>> adjListW;

public:
	int size;
	Graph(int n)
	{
		size = n;
		//adjList.resize(size);
		adjListW.resize(size);
	}
	/*void addEdgeD(int start, int end)
	{
		adjList[start].push_back(end);
	}
	void addEdgeU(int start, int end)
	{
		adjList[start].push_back(end);
		adjList[end].push_back(start);
	}*/
	void addEdgeDW(int start, int end, int weight)
	{
		adjListW[start].push_back(make_pair(end, weight));
	}
	void addEdgeUW(int start, int end, int weight)
	{
		adjListW[start].push_back(make_pair(end, weight));
		adjListW[end].push_back(make_pair(start, weight));
	}
	void MST()
	{
		int Tcost = 0, src = 0;
		priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;
		vector<int> parent(size, -1);
		vector<int> cost(size, cmax);
		vector<bool> inMST(size, false);
		pq.push(make_pair(0, src));
		cost[src] = 0;
		while (!pq.empty())
		{
			int u = pq.top().second;
			pq.pop();
			if (!inMST[u])
			{
				inMST[u] = true;
				for (auto i : adjListW[u])
				{
					int v = i.first;
					int weight = i.second;
					if (!inMST[v] && cost[v] > weight)
					{
						cost[v] = weight;
						pq.push(make_pair(cost[v], v));
						parent[v] = u;
					}
				}
			}
		}
		for (auto elem : cost)
			Tcost += elem;
		o << Tcost << endl;
		o << size - 1 << endl;
		for (int i = 1; i < size; i++)
			o << parent[i] + 1 << " " << i + 1 << endl;
	}
	void Dijkstra()
	{
		int src = 0;
		priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;
		vector<int> dist(size, dmax);
		pq.push(make_pair(0, src));
		dist[src] = 0;
		while (!pq.empty())
		{
			int u = pq.top().second;
			pq.pop();
			for (auto i : adjListW[u])
			{
				int v = i.first;
				int weight = i.second;
				if (dist[v] > dist[u] + weight)
				{
					dist[v] = dist[u] + weight;
					pq.push(make_pair(dist[v], v));
				}
			}
		}
		for (int i = 1; i < size; i++)
			if (dist[i] != dmax)
				o << dist[i] << " ";
			else
				o << 0 << " ";
	}
	void BellmanFord()
	{
		int src = 0;
		vector<int> dist(size, dmax);
		dist[src] = 0;
		for (int i = 1; i < size; i++)
			for (int u = 0; u < size; u++)
				for (auto pr : adjListW[u])
				{
					int v = pr.first;
					int weight = pr.second;
					if (dist[u] < dmax && dist[u] + weight < dist[v])
						dist[v] = dist[u] + weight;
				}
		for (int u = 0; u < size; u++)
			for (auto pr : adjListW[u])
			{
				int v = pr.first;
				int weight = pr.second;
				if (dist[u] < dmax && dist[u] + weight < dist[v])
				{
					o << "Ciclu negativ!";
					return;
				}
			}
		for (int i = 1; i < size; i++)
			if (dist[i] != dmax)
				o << dist[i] << " ";
			else
				o << 0 << " ";
	}
};

int main()
{

	int N, M;
	int x, y, w;
	f >> N >> M;
	Graph g(N);
	for (int i = 1; i <= M; i++)
	{
		f >> x >> y >> w;
		g.addEdgeDW(x - 1, y - 1, w);
	}
	//g.MST();
	//g.Dijkstra();
	g.BellmanFord();

	return 0;
}