#include<fstream>
#include<cstdio>
#include<set>
#include<stack>
#include<vector>
#include<algorithm>
#define FOR(a,b,c) for(int a=b;a<=c;++a)
#include<cstring>
#include<bitset>
#include<cmath>
#include<iomanip>
#include<queue>
#define f cin
#define g cout
#define mp make_pair
#define pb push_back
#define x first
#define y second
#define ll long long
#define inf (1<<30)
#define base 256
#define ba 255
#define N 100100
#define EPS 1e-12
#define mod  666013
#define inu "bellmanford.in"
#define outu "bellmanford.out"
using namespace std;
ifstream f(inu);
ofstream g(outu);
//int dx[]={0,0,0,1,-1};
//int dy[]={0,1,-1,0,0};
vector<pair<int,int> > v[N];
queue<int> q;
int viz[N],x,y,c,n,m,D[N];
bool bellmanford()
{
	q.push(1);
	viz[1]=1;
	while(!q.empty())
	{
		int nod=q.front();
		q.pop();
		for(int i=0;i<v[nod].size();++i)
		{
			int des=v[nod][i].first;
			int cost=v[nod][i].second;
			if(D[nod]+cost<D[des])
			{
				D[des]=D[nod]+cost;
				viz[des]++;
				q.push(des);
				if(viz[des]==n)
				return 1;
			}
		}
	}
	return 0;
}
int main ()
{
	f>>n>>m;
	FOR(i,1,m)
	{
		f>>x>>y>>c;
		v[x].push_back(make_pair(y,c));
	}
	FOR(i,2,n)
	D[i]=0x3f3f3f3f;
	if(bellmanford())
	{
		g<<"Ciclu negativ!";
		return 0;
	}
	else
	{
		FOR(i,2,n)
		g<<D[i]<<" ";
	}
    return 0;
}