#include <fstream>
#include <vector>
#include <queue>
#define inf 500000001;

using namespace std;
ifstream f("bellmanford.in");
ofstream g("bellmanford.out");
vector < pair<int, int> > a[50001];
queue <int> q;
int n,m,i,j,x,y,z,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;
}