#include <iostream>
#include <fstream>
#include <cstring>
#include <vector>

#define NMAX 500001
#define INF 0x3f3f3f3f

const char IN[] = "bellmanford.in", OUT[] = "bellmanford.out";

using namespace std;

int N, M;
vector<pair<int,int> > G[NMAX];
int dist[NMAX], pi[NMAX];

inline void readData() {
	FILE *f =freopen(IN, "r", stdin);
	if (!f) {
		fclose(stdin);  return;
	}

	scanf(" %d %d", &N, &M);
	for (int i = 0; i < M; ++i) {
		int s, d, c;
		scanf(" %d %d %d", &s, &d, &c);
		G[s].push_back(make_pair(d, c));
	}
	fclose(stdin);
}

int bellmanFord(int source) {
	memset(dist, INF, sizeof(dist));
	memset(pi, -1, sizeof(pi));
	dist[source] = 0;

	for (int vertex = 0; vertex < N; ++vertex) {
		for (int u = 1; u <= N; ++u) {
			for (auto &neigh : G[u]) {
				int v = neigh.first;
				int cost = neigh.second;
				if (dist[v] > dist[u] + cost) {
					dist[v] = dist[u] + cost;
					pi[v] = u;
				}
			}
		}
	}

	//check for negative weight cycles
	for (int u = 1; u <= N; ++u) {
		for (auto &neigh : G[u]) {
			int v = neigh.first;
			int cost = neigh.second;
			if (dist[v] > dist[u] + cost) {
				cout << "Ciclu negativ!" << endl; return 1;
			}
		}
	}
	return 0;
}


int main(void){
	readData();
	freopen(OUT, "w", stdout);
	if (bellmanFord(1)) {
		fclose(stdout);
		return 0;
	}
	else {
		for (int i = 2; i <= N; ++i) {
			cout << dist[i] << " ";
		}
		cout << endl;
		fclose(stdout);
	}

	return 0;
}