#include <fstream>
#include <vector>
#include <queue>
#define PII pair<int,int>
#define PB push_back
#define MP make_pair
#define st first
#define nd second

using namespace std;

ifstream fin("bellmanford.in");
ofstream fout("bellmanford.out");

const int INF = 0x3f3f3f3f , MAXN = 50001;
vector<PII> G[MAXN];
int D[MAXN] , countInQ[MAXN],  N , M , nod;
bool negative_cycle;

void read_data()
{
	fin>>N>>M;
	for(int x,y,c;M;M--)
		fin>>x>>y>>c , G[x].PB(MP(c,y));
}

void Bellman()
{
	bool ok[MAXN];
	queue<int> Q;
	memset(ok,false,sizeof(ok));
	memset(D,INF,sizeof(D));
	D[1] = 0;
	ok[1] = true;
	Q.push(1);
	while(!Q.empty() && !negative_cycle)
	{
		nod = Q.front() , Q.pop();
		ok[nod] = false;
		for(int i=0;i<(int)G[nod].size();++i)
			if(G[nod][i].st + D[nod] < D[G[nod][i].nd])
			{
				 D[G[nod][i].nd] = G[nod][i].st + D[nod];
				 if(!ok[G[nod][i].nd])
				 {
					if(countInQ[G[nod][i].nd]>N) negative_cycle = true;
					else
					ok[G[nod][i].nd] = true , Q.push(G[nod][i].nd) , countInQ[G[nod][i].nd]++;
				 }	
			}
	}
}

void write_data()
{
	if(negative_cycle) fout<<"Ciclu negativ!\n";
	else
	for(int i=2;i<=N;++i)
		fout<<D[i]<<' ';
}


int main()
{
	read_data();
	Bellman();
	write_data();
	return 0;
}