#include <fstream>
#include <vector>
#include <queue>
#include <cstring>

using namespace std;

#define dim 50005
#define inf 0x3f3f3f3f
#define pb push_back
#define mp make_pair
#define ff first
#define ss second
#define pii pair<int,int>

vector<pii> v[dim];
queue<int> Q;
int seen[dim],dist[dim],x,y,c,n,m;
bool in_queue[dim],negative_cycle=0;

void bellmanford(){
	
	memset(dist,inf,sizeof(dist));
	dist[1]=0;
	
	Q.push(1);
	in_queue[1]=1;
	while(!Q.empty() && !negative_cycle){
		int u = Q.front();
		Q.pop();
		in_queue[u]=0;
		for(int i=0;i<int(v[u].size());i++){
			if(dist[u]+v[u][i].ss < dist[v[u][i].ff]){
				dist[v[u][i].ff]=dist[u]+v[u][i].ss;
				if(!in_queue[v[u][i].ff]){
					Q.push(v[u][i].ff);
					seen[v[u][i].ff]++;
				}
			}
			if(seen[v[u][i].ff] > n) negative_cycle=1;
		}
	}
}

int main(){

	ifstream f("bellmanford.in");
	ofstream g("bellmanford.out");

	f >> n >> m;
	for(int i=1;i<=m;i++){
		f >> x >> y >> c;
		v[x].pb(mp(y,c));
	}

	bellmanford();

	if(negative_cycle){
		g << "Ciclu negativ!";
	}
	else{
		for(int i=2;i<=n;i++)
			g << dist[i] <<" ";
	}
}