#include <fstream>
#include <vector>
#include <queue>
using namespace std;
ifstream f ("bellmanford.in");
ofstream g ("bellmanford.out");
const int oo = 10005;
const int NMAX = 50005;
vector< pair <int, int> > v[NMAX];
int viz[NMAX], 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!";
			exit(0);
			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 == 0)
		return 0;
	for(int i = 2; i <= n; i++)
		g << d[i] << " ";
}