#include<bits/stdc++.h>
#define inf 0x3f3f3f3f 
#define maxn 50005
#define ft first
#define sd second
#define pb push_back
using namespace std; 
queue<int> q;
vector<pair<int,int> >v[maxn];
vector<pair<int,int> >::iterator it;
int n,m,cost[maxn],ind[maxn];
 
ifstream fin("bellmanford.in");
ofstream fout("bellmanford.out");

void read(){
	int x,y,c;
	fin>>n>>m;
	while(m--)
		fin>>x>>y>>c, v[x].pb({y,c});
}
 
void bellman(){
	memset(cost,inf,sizeof(cost));
	q.push(1); cost[1]=0;
	while(!q.empty()){
		int nod=q.front();
		q.pop();
		for(it=v[nod].begin(); it!=v[nod].end(); it++){
			if(cost[(*it).ft]>cost[nod]+(*it).sd){
				cost[(*it).ft]=cost[nod]+(*it).sd;
				ind[(*it).ft]++;
				if(ind[(*it).ft]>n){
					fout<<"Ciclu negativ!";
					return;
				}
				q.push((*it).ft);
			}
		}
	}
	for(int i=2; i<=n; i++)
		fout<<cost[i]<<' ';
}
 
int main(){
	read();
	bellman();
}