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

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

#pragma region Global Variables

const int maxn = 50005;

int num_vertices, num_edges;
vector< pair<int,int> > graph[maxn];
vector<int> to_visit, is_visited, dist;

#pragma endregion

#pragma region Read&Write

void Read()
{
	int a,b,c,i;

	f>>num_vertices>>num_edges;

	for(i=1;i<=num_edges;i++)
	{
		f>>a>>b>>c;
		graph[a].push_back(make_pair(b,c));
	}
}

void Write(int negative_cycle)
{
	if(negative_cycle)
		g<<"Ciclu negativ!";
	else
	{
		for(int i=2; i<=num_vertices; i++)
			g<<dist[i]<<' ';
		g<<'\n';
	}
}

#pragma endregion

int main()
{
	//Local variables
	int ok = 1, visited = 0, i, j, tovisit, vecin;
	vector<int>::iterator it;

	//Read the graph
	Read();

	//Resize vectors and assign memory
	is_visited.resize(num_vertices+1), dist.resize(num_vertices+1);
	is_visited.assign(num_vertices+1, 0), dist.assign(num_vertices+1, 1004);

	//Start Solving
	to_visit.push_back(1);
	is_visited[1] = 1;
	dist[1] = 0;
	while(visited <= num_vertices && ok)
	{
		ok = 0;
		for(i = 0; i < to_visit.size(); i++)
		{
			tovisit = to_visit[i];
			for(j = 0; j<graph[tovisit].size(); j++)
			{
				vecin = graph[tovisit][j].first;
				if(dist[vecin] > dist[tovisit] + graph[tovisit][j].second) 
				{
					dist[vecin] = dist[tovisit] + graph[tovisit][j].second;

					if(!is_visited[vecin])
						to_visit.push_back(vecin), is_visited[vecin] = 1;

					ok = 1;
				}
			}
		}

		visited++;
	}

	//Write correct solution
	Write(ok);

	return 0;
}