#include<iostream>
#include<fstream>
#include<vector>
#include<queue>
#include<utility>
#include<algorithm>

using namespace std;

const int maxn = 50010;
const int inf = 1 << 30;

vector < pair <int, int> > graf[maxn];
int m, n, nod_sursa, cost[maxn];

void read()
{
	ifstream in("bellmanford.in");
	
	int a, b, c;
	int i;
	
	in >> n >> m; nod_sursa = 1;
	
	for(i = 1; i <= m; ++i){
		in >> a >> b >> c;
		
		graf[a].push_back(make_pair(b, c));
		graf[b].push_back(make_pair(a, c));
	}
}

void solve()
{
	vector < pair <int, int> > :: iterator it;
	queue <int> Q;
	
	int nod;
	int i;
	bool f[maxn];
	
	for(i = 1; i <= n; ++i)
		cost[i] = inf;
	cost[nod_sursa] = 0;
	
	Q.push(nod_sursa);
	
	while(!Q.empty()){
		nod = Q.front();
		Q.pop();
		
		f[nod] = 0;
		
		for(it = graf[nod].begin(); it != graf[nod].end(); ++it)
			if(cost[nod] + it -> second < cost[it -> first]){
				cost[it -> first] = cost[nod] + it -> second;
				if(!f[it -> first]){
					f[it -> first] = 1;
					Q.push(it -> first);
				}
			}
	}
}

bool negativ()
{
	vector < pair <int, int> > :: iterator it;
	int i;
	
	for(i = 1; i <= n; ++i)
		for(it = graf[i].begin(); it != graf[i].end(); ++it)
			if(cost[i] + it -> second < cost[it -> first])
				return 1;
			
	return 0;
}
void write()
{
	ofstream out("bellmanford.out");
	
	int i;
	
	if(negativ())
		out << "Ciclu negativ!\n";
	else
		for(i = 1; i <= n; ++i)
			out << cost[i] << " ";
}

int main()
{
	read();
	solve();
	write();
	
	return 0;
}