#include <cstdio>
#include <queue>
#define DIM 250005
using namespace std;
const int INF = 1<<30;
struct edge
{
	int u, v, cost;
} muchii[DIM];

queue<int>Q;
int n, m, d[DIM/5], uz[DIM];

int main()
{
	FILE *f = fopen("bellmanford.in", "r");
	fscanf(f, "%d%d", &n, &m);
	for (int i = 1; i <= m; ++i)
		fscanf(f, "%d%d%d", &muchii[i].u, &muchii[i].v, &muchii[i].cost);
	
	fclose(f);
	
	for (int i = 2; i <= n; ++i)
		d[i] = INF;

	d[1] = 0;
	Q.push(1);
	int x ;
		f = fopen("bellmanford.out", "w");
	while (!Q.empty())
	{
		x = Q.front();
		Q.pop();
		for (int j = 1; j <= m; ++j)
		  if (muchii[j].u == x)
			if (d[muchii[j].u] + muchii[j].cost < d[muchii[j].v])
			{
				d[muchii[j].v] = d[muchii[j].u] + muchii[j].cost, Q.push(muchii[j].v);
				++uz[j];
				if (j == n)
				{
					fprintf (f, "Ciclu negativ!\n");
					return 0;
				}
			}
			
	}


	
		for (int i = 2; i <= n; ++i)
			fprintf(f, "%d ", d[i]==INF?-1:d[i]);
	
	fclose(f);
	
	return 0;
}