// Include
#include <fstream>
#include <cstring>
#include <vector>
#include <queue>
using namespace std;

// Definitii
#define mp make_pair
#define pb push_back

#define edge pair<int, int>
#define cost first
#define node second

// Constante
const int oo = 1061109567;
const int sz = (int)5e4+1;

// Variabile
ifstream in("bellmanford.in");
ofstream out("bellmanford.out");

int nodes, edges;

bool isInQueue[sz];
int inQueueTimes[sz];
int dist[sz];

vector<edge> graph[sz];
queue<int> q;

// Main
int main()
{
	in >> nodes >> edges;
	
	int rFrom, rTo, rCost;
	while(edges--)
	{
		in >> rFrom >> rTo >> rCost;
		graph[rFrom].pb(mp(rCost, rTo));
	}
	
	memset(dist, oo, sizeof(dist));
	
	dist[1] = 0;
	q.push(1);
	isInQueue[1] = true;
	++inQueueTimes[1];
	while(!q.empty())
	{
		int current = q.front();
		q.pop();
		isInQueue[current] = false;
		vector<edge>::iterator it, end=graph[current].end();
		for(it=graph[current].begin() ; it!=end ; ++it)
		{
			if(dist[current] + it->cost < dist[it->node])
			{
				dist[it->node] = dist[current] + it->cost;
				if(!isInQueue[it->node])
				{
					q.push(it->node);
					isInQueue[it->node] = true;
					if(++inQueueTimes[it->node] == nodes)
					{
						out << "Ciclu negativ!\n";
						in.close();
						out.close();
						return 0;
					}
				}
			}
		}
	}
	
	for(int i=2 ; i<=nodes ; ++i)
		out << dist[i] << ' ';
	
	out << '\n';
	
	in.close();
	out.close();
	return 0;
}