#include<fstream>
#include<vector>
#include<queue>
#define inf 10000001
using namespace std;

int i,j,n,m,x,y,cost1,d[50001],b[50001],c[50001];
struct per
{
	int nod,cost;
};
vector<per> a[50001];
queue<int> q;
int main()
{
	ifstream f("bellmanford.in");
	ofstream g("bellmanford.out");
	f>>n>>m;
	for(i=1;i<=m;++i)
	{
		f>>x>>y>>cost1;
		a[x].push_back((per) {y,cost1});
	}
	for(i=2;i<=n;++i)
		d[i]=inf,b[i]=0,c[i]=0;
	d[1]=0;
	q.push(1);
	int ok=0;
	while(!q.empty()&&!ok)
	{
		x=q.front();
		b[x]=0;
		for(i=0;i<a[x].size();++i)
			if(d[x]<inf)
				if(d[a[x][i].nod]>d[x]+a[x][i].cost)
				{
					d[a[x][i].nod]=d[x]+a[x][i].cost;
					if(!b[a[x][i].nod])
					{
						if(c[a[x][i].nod]>n)
							ok=1;
						else
						{
							q.push(a[x][i].nod);
							b[a[x][i].nod]=1;
							++c[a[x][i].nod];
						}
					}
				}
				q.pop();
	}
	if(!ok)
	{
		for(i=2;i<=n;++i)
			g<<d[i]<<" ";
	}
		else
			g<<"Ciclu negativ!";
		return 0;
}