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

#define INF 2000000000
#define NMax 50010

using namespace std;

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

vector< pair<int, int> > G[NMax];
queue<int> qu;
int nodes, edges, n1, n2, c, passes[NMax], dist[NMax];

bool BF_BFS(int node)
{
	for (int i = 1; i <= nodes; i++)
		if (i != node)
			dist[i] = INF;

	dist[node] = 0;

	qu.push(node);

	while (!qu.empty()) {

		int cnode = qu.front();
		passes[cnode]++;

		if (passes[cnode] == nodes) {
			g << "Ciclu negativ!";
			return false;
		}

		for (vector< pair<int, int> >::iterator it = G[cnode].begin(); it != G[cnode].end(); it++) {
			
			if (dist[cnode] + it->second < dist[it->first]) {
				dist[it->first] = dist[cnode] + it->second;
				qu.push(it -> first);
			}

		}

		qu.pop();

	}

	return true;
}

int main()
{
	f >> nodes >> edges;

	for (int i = 1; i <= edges; i++) {
		f >> n1 >> n2 >> c;

		G[n1].push_back(make_pair(n2, c));
	}

	if (BF_BFS(1)) 
		for (int i = 2; i <= nodes; i++)
			g << dist[i] << " ";

	return 0;
}