#include<iostream>
#include<fstream>
#include<vector>
#include<queue>
using namespace std;

#define NMAX 50001
#define INF 1<<30

struct muchie {
	int y,cost;
};

vector <muchie> v[NMAX];
queue <int> c;
int d[NMAX],viz[NMAX];

int main ()
{
	int n,m,i,x,nod;
	muchie aux;
	ifstream f("bellmanford.in");
	ofstream g("bellmanford.out");
	f>>n>>m;
	for(i=1;i<=m;i++) {
		f>>x>>aux.y>>aux.cost;
		v[x].push_back(aux);
	}
	f.close();
	c.push(1);
	viz[1]=1;
	for(i=2;i<=n;i++)
		d[i]=INF;
	while(c.empty()==0) {
		nod=c.front();
		c.pop();
		for(vector <muchie> :: iterator it=v[nod].begin();it!=v[nod].end();it++) {
			if(d[nod]+it->cost<d[it->y]) {
				d[it->y]=d[nod]+it->cost;
				c.push(it->y);
				viz[it->y]++;
				if(viz[it->y]>n) {
					g<<"Ciclu negativ!\n";
					g.close();
					return 0;
				}
			}
		}
	}
	for(i=2;i<=n;i++)
		g<<d[i]<<" ";
	g.close();
	return 0;
}