#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];
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(int it=0; it<v[nod].size(); it++){
			if(ind[v[nod][it].ft]>n){
					cout<<"Ciclu negativ!";
					return;
			}
			if(cost[v[nod][it].ft]>cost[nod]+v[nod][it].sd){
				cost[v[nod][it].ft]=cost[nod]+v[nod][it].sd;
				ind[v[nod][it].ft]++;
				q.push(v[nod][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();
}