#include <iostream>
#include <fstream>
#include <queue>   
#include <vector>
#include <stdio.h>

#define INF 0x7fffffff
#define NMAX 50002

using namespace std;
ifstream f("dijkstra.in");
ofstream g("dijkstra.out");
struct Nod {
    int nod;
    int distanta;
	bool operator<(const Nod &o) const
	{
		return distanta > o.distanta;
	}

};
vector < vector < Nod > > G(NMAX);
vector < int > dist(NMAX, INF);
vector < bool > vizitat(NMAX);
vector < int > cnt_nod_inQ(NMAX, 0);
int n, m;

bool compare (const Nod& a, const Nod& b) {
    return a.distanta < b.distanta;
}

void read() {
	FILE * pFile;

	pFile = fopen("bellmanford.in", "r");
    //f >> n >> m;
	fscanf(pFile, "%d %d", &n, &m);
	int x = 0, y = 0, dist = 0;
	Nod nod_pereche;
    while (m--) {
		fscanf(pFile, "%d %d %d", &x, &y, &dist);
        
        nod_pereche.nod = y;
        nod_pereche.distanta = dist;
		G[x].push_back(nod_pereche);
    }
}
Nod constructNode(int nod, int distanta) {
	Nod new_node;
	new_node.nod = nod;
	new_node.distanta = distanta;
	return new_node;
}
void solve() {
	priority_queue<Nod> qNod;
	dist[1] = 0;
	Nod new_node = constructNode(1, 0);
	qNod.push(new_node);
	bool isNegative = false;
	while (!qNod.empty() && !isNegative) {
		int nod = qNod.top().nod;
		qNod.pop();
		for (int i = 0; i < G[nod].size(); i++) {
			int to = G[nod][i].nod;
			int dist_to = G[nod][i].distanta;
			if (dist_to + dist[nod] < dist[to]) {
				Nod copy_node = constructNode(to, dist_to + dist[nod]);
				qNod.push(copy_node);
				cnt_nod_inQ[to]++;
				if (cnt_nod_inQ[to] >= n) {
					isNegative = true;
					break;
				}
				dist[to] = dist_to + dist[nod];
			}

			vizitat[nod] = true;
		}
		
	}
	FILE * pFile;

	pFile = fopen("bellmanford.out", "w");
	if (isNegative) {
		fprintf(pFile, "Ciclu negativ!");
		return;
	}
	for (int i = 2; i <= n; i++) {
		if (dist[i] == INF) {
			dist[i] = 0;
		}
		fprintf(pFile, "%d ", dist[i]);
		
	}
}
int main()
{
    read();
	solve();
    return 0;
}