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

// Definitii
#define pb push_back
#define mp make_pair

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

// Constante
const int sz = (int)5e4+1;
const int oo = (1<<30)-1;

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

int nodes, edges;
int dist[sz];

int inQueueTimes[sz];
bool inQueue[sz];

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

// Main
int main()
{
	in >> nodes >> edges;
	
	int rFrom, rTo, rCost;
	while(edges--)
	{
		in >> rFrom >> rTo >> rCost;
		graph[rFrom].pb(mp(rTo, rCost));
	}
	
	for(int i=2 ; i<=nodes ; ++i)
		dist[i] = oo;
	
	bfQueue.push(1);
	inQueue[1] = true;
	inQueueTimes[1] = 1;
	
	while(!bfQueue.empty())
	{
		int currentNode = bfQueue.front();
		bfQueue.pop();
		inQueue[currentNode] = false;
		
		vector<edge>::iterator it, end=graph[currentNode].end();
		for(it=graph[currentNode].begin() ; it!=end ; ++it)
		{
			if(dist[currentNode] + it->cost < dist[it->node])
			{
				dist[it->node] = dist[currentNode] + it->cost;
				if(inQueue[it->node])
					continue;
				
				bfQueue.push(it->node);
				inQueue[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;
}