#include<fstream>
#include<vector>
#include<queue>
#include<bitset>
#include<string.h>
using namespace std;

const int INF=0x3f3f3f3f, MAX_N=50001;
int timesInQ[MAX_N];

int main(){
	ifstream in("bellmanford.in");
	int n,m,x,y,c;
	in>>n>>m;
	vector<pair<int,int> > adj[n+1];
	while(m--){
		in>>x>>y>>c;
		adj[x].push_back(make_pair(y,c));
	}
	in.close();
	
	bool negativeCycle=false;
	queue<int> q;
	bitset<MAX_N> inQueue(false);
	int dist[n+1];
	memset(dist,INF, sizeof dist);  
	vector< pair<int, int> > :: iterator it;
	
	q.push(1); dist[1]=0; timesInQ[1]=1; inQueue[1]=true;
	
	while(!q.empty() && !negativeCycle){
	     x=q.front(); q.pop(); inQueue[x]=false;
		   for(it=adj[x].begin(); it!=adj[x].end(); it++)
		   	  if(dist[x]+it->second < dist[it->first]){
		   	  	     dist[it->first]=dist[x]+it->second;
		   	  	     if(timesInQ[it->first]>n) negativeCycle=true;
		   	  	     else{
		   	  	        q.push(it->first);
						inQueue[it->first]=true;
						timesInQ[it->first]++;
					 }
				 }	
	}
	
	freopen("bellmanford.out","w",stdout);
	if(negativeCycle) {
		printf("Ciclu negativ!"); 
		return 0;
	}
	for(int i=2;i<=n;i++) printf("%d ",dist[i]);
	
	return 0;
}