#include <fstream>
#include <map>
#include <vector>
#include <queue>

using namespace std;

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

const int INF=1<<30;

map<int, vector<pair<int,int> > > graph;
map<int,int> cost;
map<int,int> app; // appereances of a vertex
int edges,vertices;

void read(){
	in>>vertices>>edges;
	int x,y,c;
	for(int i=1;i<=edges;++i){
		in>>x>>y>>c;
		graph[x].push_back(make_pair(y,c));
	}
}

void BellmanFord(){
	int i;
	for(i=1;i<=vertices;++i){
		cost[i]=INF;
		app[i]=0;
	}
	cost[1]=0;
	queue<int> Q;
	Q.push(1);
	int currentvertex;
	vector<pair<int,int> >::iterator it;
	pair<int,int> currentpair;
	while(!Q.empty()){
		currentvertex=Q.front();
		Q.pop();
		for(it=graph[currentvertex].begin();it!=graph[currentvertex].end();++it){
			currentpair=*it;
			if(cost[currentpair.first]>cost[currentvertex]+currentpair.second){
				Q.push(currentpair.first);
				cost[currentpair.first]=cost[currentvertex]+currentpair.second;
				app[currentpair.first]++;
				if(app[currentpair.first]>vertices && cost[currentpair.first]<0){
					out<<"Ciclu negativ!";
					return;
				}
			}
		}			
	}
	for(i=2;i<=vertices;++i){
		out<<cost[i]<<" ";
	}
}

int main(){
	read();
	BellmanFord();
	return 0;
}