#include<fstream>
#include<vector>
#include<list>
#include<iostream>
#include<queue>

#define NMAX 50005
#define MMAX 250005

using namespace std;

long n,m;
struct muchie
{
	long vf1,vf2,cost,loc;
	muchie(){}
	muchie(long nvf1,long nvf2, long ncost, long nloc) : vf1(nvf1), vf2(nvf2), cost(ncost), loc(nloc){}

};

long long d[NMAX];
long vizitat[NMAX];
vector<list<muchie> > V;
int main()
{
	long i,x,y,cost;
	fstream fin,fout;
	queue<long> Q;

	fin.open("dijkstra.in",ios::in);
	fout.open("dijkstra.out",ios::out);
	list<muchie> lista;

	fin>>n>>m;

	for(i=0;i<=n;i++)
	{
		d[i]=LONG_MAX;
		V.push_back(lista);
	}
	d[1]=0;

	for(i=1;i<=m;i++)
	{
		fin>>x>>y>>cost;
	//	E.push_back(muchie(x,y,cost));
		V[x].push_back(muchie(x,y,cost,i));
	}
	list<muchie>::iterator itr;
	Q.push(1);
	long varf;
	vizitat[1]=1;
	int ok=1;

	while(!Q.empty() && ok==1)
	{
		varf=Q.front();
		Q.pop();
		if(vizitat[varf]>n)
			ok=0;
		vizitat[varf]++;

		for(itr=V[varf].begin(); itr!=V[varf].end(); itr++)
			if(d[(*itr).vf2]>d[(*itr).vf1]+(*itr).cost)
			{
				d[(*itr).vf2]=d[(*itr).vf1]+(*itr).cost;
				Q.push((*itr).vf2);
			}
		
	}

	for(i=1;i<=n && ok==1;i++)
	{
		for(itr=V[i].begin(); itr!=V[i].end(); itr++)
			if(d[(*itr).vf2]>d[(*itr).vf1]+(*itr).cost)
				ok=0;
	}

	if(ok==0)
		fout<<"Ciclu negativ!";
	else
		for(i=2;i<=n;i++)
			fout<<d[i]<<" ";
	fout<<'\n';

	fin.close();
	fout.close();
	return 0;
}