#include <stdio.h>
#include <iostream>
#include <fstream>
#include <vector>
#include <array>
#include <algorithm>
#include <vector>
#include <stack>
#include <set>
#include <assert.h>
#include <queue>
#include <chrono>
#include <memory>
#include <cstring>
#include <stdexcept>
 
using LL = long long;
using ULL = int long long;
 
const std::string _problemName = "bellmanford";
 
#define USE_FILES
 
#ifdef USE_FILES
 
namespace std {
std::ifstream fin(_problemName + ".in");
std::ofstream fout(_problemName + ".out");
}
 
#define cin fin
#define cout fout
#endif

struct Edge {
	int toNode;
	int cost;
	
	Edge(int toNode, int cost): toNode(toNode), cost(cost) {}
};

using graph = std::vector< std::vector<Edge> >;
const int INF = 0x3f3f3f3f;

std::vector<int> computeMinDistances(const graph& g, int startNode) {
	std::vector<int> minDistances(g.size(), INF);
	
	std::vector<int> timesInQueue(g.size(), 0);
	std::vector<bool> inQueue(g.size(), false);
	
	std::queue<int> candidates;
	
	minDistances[startNode] = 0;
	candidates.push(startNode);
	inQueue[startNode] = true;
	
	while (!candidates.empty()) {
		int current = candidates.front();
		candidates.pop();
		
		inQueue[current] = false;
		if (++timesInQueue[current] > g.size()) {
			throw std::invalid_argument("Fail");
		}
		
		for (auto neighbourEdge : g[current]) {
			int neighbour = neighbourEdge.toNode;
			int costToNeighbour = neighbourEdge.cost;
			
			if (minDistances[neighbour] > minDistances[current] + costToNeighbour) {
				minDistances[neighbour] = minDistances[current] + costToNeighbour;
				
				if (!inQueue[neighbour]) {
					candidates.push(neighbour);
					inQueue[neighbour] = true;
				}
			}
		}
	}
	
	return minDistances;
}

int main() {
	int n, m;
	std::cin >> n >> m;

	graph g(n);	
	
	for (int edgeIdx = 0; edgeIdx < m; ++edgeIdx) {
		int x, y, c;
		std::cin >> x >> y >> c;
		--x, --y;
		
		g[x].emplace_back(y, c);
	}
	
	try {
		std::vector<int> distances = computeMinDistances(g, 0);
	
		for (int node = 1; node < n; ++node) {
			std::cout << distances[node] << ' ';
		}
		std::cout << '\n';
	}
	catch (...) {
		std::cout << "Ciclu negativ!" << '\n';
	}
	
	return 0;
}