#include <fstream>
#include <vector>
#include <queue>
using namespace std;
ifstream f ("/home/mihai/Documents/C++/004Bellman_Ford/bellmanford.in");
ofstream g ("/home/mihai/Documents/C++/004Bellman_Ford/bellmanford.out");
const int oo = 1005;
const int NMAX = 50005;
vector< pair <int, int> > v[NMAX];
int viz[NMAX];
int d[NMAX];
queue <int> coada;
int n, m, ok = 1;
void bellmanford()
{
	coada.push(1);
	for(int i = 2; i <= n; i++)
		d[i] = oo;
	while(!coada.empty())
	{
		int nodCurent = coada.front();
		coada.pop();
		if(viz[nodCurent] > n + 1)
		{
			g << "Ciclu negativ!";
			ok = 0;
			return;
		}
		viz[nodCurent]++;
		for(int i = 0; i < v[nodCurent].size(); i++)
		{
			int vecin = v[nodCurent][i].first;
			int cost = v[nodCurent][i].second;
			if(d[vecin] > d[nodCurent] + cost)
			{
				d[vecin] = d[nodCurent] + cost;
				coada.push(vecin);
			}
		}
	}
}
 
int main()
{
	f >> n >> m;
	while(m--)
	{
		int x, y, c;
		f >> x >> y >> c;
		v[x].push_back(make_pair(y,c));
	}
	bellmanford();
	if(ok == 1)
		for(int i = 2; i <= n; i++)
			g << d[i] << " ";
}