#include<fstream>
#include<vector>
#include<queue>
#define mn INT_MIN
#define asd 50002
using namespace std;
vector<long long> v[asd],c[asd];
queue<long long> q;
long long d[asd];
bool viz[asd];
long long m,n;
void citire()
{
	long long i,x,y,e;
	ifstream in("bellmanford.in");
	in>>n>>m;
	for (i=1;i<=m;i++)
	{
		in>>x>>y>>e;
		v[x].push_back(y);
		c[x].push_back(e);
	}
	//for (i=1;i<=n;i++)
	//	d[i]=mn;
}
void af()
{
	ofstream out("bellmanford.out");
	out<<"Ciclu negativ!";
	out.close();
	
}
void afisare()
{
	long long i;
	ofstream out("bellmanford.out");
	for (i=2;i<=n;i++)
		out<<d[i]<<" ";
	out<<'\n';
}
	
int main()
{
	long long i,x,y,ok=1;	
	citire();
	q.push(1);
	d[1]=0;
	viz[1]=1;
	while (!q.empty()&&ok)
	{
		x=q.front();
		q.pop();
		
		for (i=0;i<(long long)v[x].size();i++)
		{
			y=v[x][i];
			if (!viz[y])
			{
				//if (d[y]>d[x]+c[x][i])
				{
					d[y]=d[x]+c[x][i];
					q.push(y);
					viz[y]=1;
				}				
			}
			else if (d[x]+c[x][i]<d[y])
			{
				d[y]=d[x]+c[x][i];
				q.push(y);		
				//if (d[y]<0)
					//ok=0;
			}
			if ((int)q.size()>n)
				ok=0;			
		}
	}
	if (ok)
		afisare();
	else
		af();
}