#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];

void read(){
	int x,y,c;
	cin>>n>>m;
	while(m--)
		cin>>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(ind[(*it).ft]>n){
					cout<<"Ciclu negativ!";
					return;
			}
			if(cost[(*it).ft]>cost[nod]+(*it).sd){
				cost[(*it).ft]=cost[nod]+(*it).sd;
				ind[(*it).ft]++;
				q.push((*it).ft);
			}
		}
	}
	for(int i=2; i<=n; i++)
		cout<<cost[i]<<' ';
}

int main(){
	freopen("bellmanford.in","r",stdin);
	freopen("bellmanford.out","w",stdout);
	read();
	bellman();
}