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

using namespace std;

const char iname[] = "bellmanford.in";
const char oname[] = "bellmanford.out";
const int  nmax	   = 50006;

ifstream fin(iname);
ofstream fout(oname);

int n, m, i, x, y, c;
int d[nmax], viz[nmax], cnt[nmax];

vector<pair <int, int> > Gr[nmax];
queue<int> Q;

void dijkstra()
{	
	int i, x;
	Q.push(1);
	d[1] = 0;
	viz[1] = 1;
	cnt[1] = 1;
	for(i = 2; i <= n; i ++)
		d[i] = 218989982;
	while(!Q.empty())
	{
		x = Q.front();
		viz[x] = 0;
		cnt[x]++;
		if(cnt[x] >= n)
		{
			fout << "Ciclu negativ!\n";
			exit(0);
		}
		Q.pop();
		for(vector<pair <int, int> >::iterator it = Gr[x].begin(); it != Gr[x].end(); ++it)
		{
				if(d[x] + it->second < d[it->first])
				{
					d[it -> first] = d[x] + it->second;
					if(!viz[it ->first])
					{
						viz[it -> first] = 1;
						Q.push(it -> first);
					}
				}	
	
		}
	}
}

int main()
{
	fin >> n >> m;
	for(i = 1; i <= m; i ++)
	{
		fin >> x >> y >> c;
		Gr[x].push_back(make_pair(y, c));
	}
	
	dijkstra();
	for(i = 2; i <= n; i ++)
	{
		if(d[i] == 218989982)
			fout << "0 ";
		else
			fout << d[i] << " ";
	}
	return 0;
}