#include<fstream>
#include<iostream>
#include<vector>
#include<queue>
#include<utility>
#define INF 1000000000

using namespace std;

vector < pair < int, int > > *adj;
vector <int> dist, e; // e = vector care marcheaza existenta in coada
int n, m, u, v, c, i, nrPasi;
queue<int> q;

void init(int s)
{
	for(i = 0; i < n; i++)
	{
		dist[i] = INF;
		e[i] = 0;
	}
	dist[s] = 0;
}

void relax(int u, int v) // v este nr. nodului din lista de vecini a lui u
{
	if(dist[adj[u][v].first] > dist[u] + adj[u][v].second)
	{
		dist[adj[u][v].first] = dist[u] + adj[u][v].second;
		if(!e[adj[u][v].first])  // daca v s-a modificat si nu e in coada, il adaugam
		{
			q.push(adj[u][v].first);
			e[adj[u][v].first] = 1;
		}
	}
}

int main()
{
	ifstream fin("bellmanford.in");
	ofstream fout("bellmanford.out");
	fin >> n >> m;
	adj = new vector < pair < int, int > >[n];
	dist.resize(n);
	e.resize(n);
	for(i = 0; i < m; i++)
	{
		fin >> u >> v >> c;
		adj[u - 1].push_back(make_pair(v - 1, c));
	}
	init(0);
	q.push(0);
	e[0] = 1;
	while(!q.empty())
	{
		u = q.front();
		q.pop();
		nrPasi++;
		if(nrPasi > m)
		{
			fout << "Ciclu negativ!";
			return 0;
		}
		e[u] = 0;
		for(i = 0; i < (int)adj[u].size(); i++)
		{
			relax(u, i);
		}
	}
	for(i = 1; i < n; i++)
		fout << dist[i] << " ";
	return 0;
}