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

#define nmax 50001
long n, m;
vector < pair<long, long> > v[nmax];
queue <long> Q;
long d[nmax], viz[nmax];

inline void citire()
{
	long x, y, c;
	ifstream in("bellmanford.in"); in>>n>>m;
	for(long i=1; i<=m; i++)
	{
		in>>x>>y>>c;
		v[x].push_back( make_pair(y, c) );
	}
}

inline void afisare(bool ciclu)
{
	ofstream out("bellmanford.out");
	if(ciclu)
		out<<"Ciclu negativ!";
	else
		for(long i=2; i<=n; i++)
			out<<d[i]<<" ";
}

int bellman_ford()
{
	long nod; 
	vector< pair<long, long> >::pointer next;
	Q.push(1);

	while(!Q.empty())
	{
		nod = Q.front(); Q.pop();
		for(long i=0; i<v[nod].size(); i++)
		{
			next = &v[nod][i];
			if(d[nod]+next->second < d[next->first] || d[next->first]==0 )
			{
				d[next->first] = d[nod] + next->second;
				viz[next->first]++;
				if(viz[next->first] > n)
					return 0;
				Q.push(next->first);
			}
		}
	}
	return 1;
}

int main()
{
	citire();
	if( bellman_ford() )
		afisare(0);
	else
		afisare(1);
	return 0;
}