#include<fstream>
#include<vector>
#include<queue>
#define inf 500000001;
using namespace std;
vector <pair <int,int> > a[50001];
queue < int > q;
ifstream f("bellmanford.in");
ofstream g("bellmanford.out");
int n,m,x,y,z,i,j,viz[50001],d[50001],nr[50001];
int main(){
	f>>n>>m;
	for (i=1;i<=m;i++){
		f>>x>>y>>z;
		a[x].push_back(make_pair(y,z));
	}
	d[1]=0;
	for (i=2;i<=n;i++)
		d[i]=inf;
	q.push(1);
	viz[1]=1;
	while (!q.empty()){
		int k=(int)q.front();
		for(i=0;i<a[k].size();i++){
			int v=(int)a[k][i].first;
			int c=(int)a[k][i].second;
			if (d[v]>d[k]+c){
				d[v]=d[k]+c;
				nr[v]++;
				if(nr[v]>=n){
					g<<"Ciclu negativ!";
					return 0;
				}
				if(viz[v]==0){
					q.push(v);
					viz[v]=1;
				}
			}
		}
		q.pop();
		viz[k]=0;
	}
	for (i=2;i<=n;i++)
		g<<d[i]<<" ";
	return 0;
}