#include <fstream>
#include <vector>
#include <cstring>
#include <queue>
#include <bitset>
#define MAX_NODES 50000
#define INF 0x7f7f7f7f
using namespace std;
ifstream fin("bellmanford.in");
ofstream fout("bellmanford.out");

vector<pair<int, int>> directedGraph[MAX_NODES + 1];
int distances[MAX_NODES + 1];
queue<int> nodesToVisit;
bitset<MAX_NODES + 1> isInNodesToVisit;
int cntOccurrences[MAX_NODES + 1];

void bellmanFord(int startNode, int nrNodes) {
	memset(distances, INF, sizeof distances);
	distances[startNode] = 0;
	nodesToVisit.push(startNode);
	cntOccurrences[startNode]++;
	while (!nodesToVisit.empty()) {
		int node = nodesToVisit.front();
		nodesToVisit.pop();
		isInNodesToVisit[node] = false;
		for (pair<int, int> neighbour : directedGraph[node]) {
			if (distances[node] + neighbour.second < distances[neighbour.first]) {
				distances[neighbour.first] = distances[node] + neighbour.second;
				++cntOccurrences[neighbour.first];
				/*Detect negative cycle*/
				if (cntOccurrences[neighbour.first] > nrNodes) {
					fout << "Ciclu negativ!";
					return;
				}
				if (!isInNodesToVisit[neighbour.first]) {
					nodesToVisit.push(neighbour.first);
					isInNodesToVisit[neighbour.first] = true;
				}
			}
		}
	}
	for (int node = 2; node <= nrNodes; ++node) {
		fout << distances[node] << ' ';
	}
}

int main() {
	int nrNodes, nrEdges;
	fin >> nrNodes >> nrEdges;
	for (int edge = 0; edge < nrEdges; ++edge) {
		int sourceNode, destinationNode, edgeCost;
		fin >> sourceNode >> destinationNode >> edgeCost;
		directedGraph[sourceNode].push_back({ destinationNode, edgeCost });
	}
	bellmanFord(1, nrNodes);
	return 0;
}