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