// http://infoarena.ro/problema/bellmanford
#include <fstream>
#include <vector>
#include <queue>
using namespace std;

#define location first
#define cost second

const int MAXSIZE = 50001;
const int oo = 0x3f3f3f3f;

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

int nodes,edges;
bool visit[MAXSIZE];
int timesVisited[MAXSIZE];
vector<int> dist(MAXSIZE,oo);
vector< pair<int,int> > graph[MAXSIZE];
queue<int> nodesQueue;

bool bellmanFord(int startNode);

int main() {
	in >> nodes >> edges;
	
	int from,to,cost;
	for(int i=1;i<=edges;i++) {
		in >> from >> to >> cost;
		graph[from].push_back(make_pair(to,cost));
	}
	in.close();
	
	if(!bellmanFord(1))
		out << "Ciclu negativ!";
	else
		for(int i=2;i<=nodes;i++)
			out << dist[i] << " ";
	out << "\n";
	
	out.close();
	
	return (0);
}

bool bellmanFord(int startNode) {
	dist[startNode] = 0;
	nodesQueue.push(startNode);
	
	int node;
	vector< pair<int,int> >::iterator it,end;
	
	while(!nodesQueue.empty()) {
		node = nodesQueue.front();
		nodesQueue.pop();
		
		end = graph[node].end();
		
		for(it=graph[node].begin();it!=end;++it)
			if(dist[it->location] > dist[node] + it->cost) {
				dist[it->location] = dist[node] + it->cost;
				
				if(!visit[it->location]) {
					timesVisited[it->location]++;
					if(timesVisited[it->location] > nodes)
						return false;
				}
				
				nodesQueue.push(it->location);
				visit[it->location] = true;
			}
		
		visit[node] = false;
	}
	
	return true;
}