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

#define NMAX 50001
#define INF (1<<30)

struct Nod {
	int y,cost;
	Nod() {
		y=0;
		cost=0;
	}
	inline Nod(int _y, int _cost) {
		y=_y;
		cost=_cost;
	}
	inline bool operator < (const Nod &x) const {
		return cost>x.cost;
	}
};

priority_queue <Nod> c;
queue <int> q;
int viz[NMAX],inq[NMAX];

class Graph {
	
	vector <Nod> v[NMAX];
	int n;
	
public:
	
	Graph (int _n) {
		n=_n;
	}
	
	Graph () {
		n=0;
	}
	
	void addEdge(int x, int y, int cost = 0) {
		v[x].push_back(Nod(y,cost));
	}
	
	void setNodes(int _n) {
		n=_n;
	}
	
	void dijkstra(int nod, int d[]) {
		int i;
		for(i=1;i<=n;i++) {
			d[i]=INF;
			viz[i]=0;
		}
		d[nod]=0;
		c.push(Nod(nod,0));
		while(c.empty()==0) {
			nod=c.top().y;
			c.pop();
			if(viz[nod]==0) {
				viz[nod]=1;
				for(vector <Nod> :: iterator it=v[nod].begin();it!=v[nod].end();it++) 
					if(d[it->y]>d[nod]+it->cost) {
						d[it->y]=d[nod]+it->cost;
						c.push(Nod(it->y,d[it->y]));
					}
			}
		}
	}
	
	int BellmanFord(int nod, int d[]) {
		int i;
		for(i=1;i<=n;i++) {
			d[i]=INF;
			viz[i]=0;
		}
		d[nod]=0;
		q.push(nod);
		viz[nod]=1;
		while(q.empty()==0) {
			nod=q.front();
			q.pop();
			for(vector <Nod> :: iterator it=v[nod].begin();it!=v[nod].end();it++) {
				if(d[it->y]>d[nod]+it->cost) {
					d[it->y]=d[nod]+it->cost;
					q.push(it->y);
					viz[it->y]++;
					if(viz[it->y]>=n-1)
						return 1;
				}
			}
		}
		return 0;
	}
};

Graph G;
int d[NMAX];

int main ()
{
	int n,m,i,x,y,cost;
	ifstream f("bellmanford.in");
	ofstream g("bellmanford.out");
	f>>n>>m;
	G.setNodes(n);
	for(i=1;i<=m;i++) {
		f>>x>>y>>cost;
		G.addEdge(x,y,cost);
	}
	f.close();
	if(G.BellmanFord(1,d)==1)
		g<<"Ciclu negativ!";
	else {
		for(i=2;i<=n;i++) 
			g<<d[i]<<" ";
	}
	g<<'\n';
	g.close();
	return 0;
}