#include<cstdio>
#include<queue>
#include<vector>

using namespace std;

const int N=50001;
const int INF = 1<<30;

struct NOD {int y, cost;};
int n,m,x,i, d[N], nrq[N];
bool inq[N];

vector <NOD> a[N];
queue <int> q;


int main()
{
	freopen ("bellmanford.in" , "r" , stdin );
	freopen ("bellmanford.out" , "w" , stdout );
	
	scanf ("%d%d" , &n , &m );
	int x, y, cost;
	for (int i=1 ; i<=m ; ++i)
	{
		scanf("%d%d%d" , &x , &y , &cost);
		a[x].push_back((NOD){y,cost});
	}
	
	for (int i=1 ; i<=N ; ++i)
		d[i] = INF;
	
	q.push(1);
	d[1]=0;

	while(!q.empty())
	{
		x = q.front();
		q.pop();
		inq[x] = false;
		for(size_t i=0 ; i<a[x].size() ; ++i)
		{
			y = a[x][i].y;
			if (d[x]+a[x][i].cost<d[y])
			{
				d[y] = d[x] + a[x][i].cost;
				if (!inq[y])
				{
					q.push(y);
					inq[y] = true;
					nrq[y]++;
					if(nrq[y]==n)
					{
						printf("Ciclu negativ!\n");
						return 0;
					}
				}
			}
		}
	}
	
	for(int i=2 ; i<=n ; ++i )
		printf("%d ", d[i]);
	
	return 0;
}