#include<fstream>
#include<cstdio>
#include<vector>
#include<queue>

using namespace std;

const int MaxN = 50001;
const int Inf = 0x3f3f3f3f;

const char InFile[] = "bellmanford.in";
const char OutFile[] = "bellmanford.out";

int N,M,ok,d[MaxN],viz[MaxN];
vector< pair<int,int> > G[MaxN];
queue<int> Q;

void Bellman_Ford()
{
	int nod;
	vector< pair<int,int> >::iterator it;
	for( nod = 1 ; nod <= N ; ++nod )
		d[nod] = Inf;
	d[1] = 0;
	Q.push(1);
	while( !Q.empty() )
		{
			nod = Q.front();
			Q.pop();
			for( it = G[nod].begin() ; it != G[nod].end() ; ++it )
				if( d[it->first] > d[nod] + it->second )
					{
						d[it->first] = d[nod] + it->second;
						Q.push(it->first);
						viz[it->first]++;
						if( viz[it->first] > N )
							{
								ok = 0;
								return;
							}
					}
		}
}

int main()
{
	ifstream fin( InFile );
	ofstream fout( OutFile );
	fin >> N >> M;
	int i,x,y,cost;
	for( i = 0  ; i < M ; ++i )
		{
			fin >> x >> y >> cost;
			G[x].push_back(make_pair(y,cost));
		}
	ok = 1;
	Bellman_Ford();
	if( !ok )
		fout << "Ciclu negativ!";
		else
		for( i = 2 ; i <= N ; ++i )
			fout << d[i] << ' ';
	fout << '\n';
	fin.close();
	fout.close();
	return 0;
}