#include <cstdio>

struct vertex
{
	unsigned short number;
	signed short path;
};

struct list_element
{
	struct vertex node;
	struct list_element *next;
};

const signed int MAX_VERTICES(50000);
const signed int MAX_EDGES(250000);
const signed int MAX_PATH(1000);
const signed int LONGEST_POSSIBLE_PATH(MAX_EDGES * MAX_PATH);

struct list_element *graph [MAX_VERTICES];
signed int shortest_path [MAX_VERTICES];
bool availeable [MAX_VERTICES];
unsigned short total_updates [MAX_VERTICES];
unsigned short update [MAX_VERTICES];

bool BellmanFord (unsigned int n)
{
	unsigned short node, neighbor, *update_top(update), *update_push(update + 1), updating_paths(1);
	const unsigned short *const END(update + n);
	signed int distance, new_distance;
	struct list_element *iterator;
	do
	{
		node = *update_top;
		++update_top;
		if (update_top == END)
			update_top = update;
		distance = shortest_path[node];
		availeable[node] = false;
		--updating_paths;
	    for (iterator = graph[node] ; iterator ; iterator = iterator->next)
	    {
	    	neighbor = iterator->node.number;
	    	new_distance = distance + iterator->node.path;
	    	if (new_distance < shortest_path[neighbor])
	    	{
	    		shortest_path[neighbor] = new_distance;
	    		if (availeable[neighbor])
	    			continue;
	    		++total_updates[neighbor];
	    		if (total_updates[neighbor] == n)
	    			return true;
	    		availeable[neighbor] = true;
	    		*update_push = neighbor;
	    		++update_push;
	    		if (update_push == END)
	    			update_push = update;
	    		++updating_paths;
	    	}
	    }
	}
	while (updating_paths);
	return false;
}

int main (void)
{
	unsigned int n,m;
	std::freopen("bellmanford.in","r",stdin);
	std::scanf("%u%u",&n,&m);
	unsigned short node1, node2;
	signed short path;
	char node1_string[6] = {'\0'}, node2_string[6] = {'\0'}, path_string[6] = {'\0'};
	char *number;
	char ch;
	bool negative;
	struct list_element *new_element;
	do
	{
	    node1 = node2 = path = 0;
	    negative = false;
		std::scanf("%s%s%s",node1_string,node2_string,path_string);
		number = node1_string;
		do
		{
		    ch = *number - '0';
			node1 *= 10;
			node1 += ch;
	    	++number;
		}
		while (*number);
		number = node2_string;
		do
		{
			ch = *number - '0';
			node2 *= 10;
			node2 += ch;
			++number;
		}
		while (*number);
		number = path_string;
		if (*number == '-')
		{
			negative = true;
			++number;
	    }
	    do
	    {
	    	ch = *number - '0';
	    	path *= 10;
	    	path += ch;
	    	++number;
	    }
	    while (*number);
	    if (negative)
	        path = -path;
		--node1;
		--node2;
		new_element = new struct list_element;
		new_element->node.number = node2;
		new_element->node.path = path;
		new_element->next = graph[node1];
		graph[node1] = new_element;
		--m;
	}
	while (m);
	std::fclose(stdin);
	signed int *iterator(shortest_path + 1);
	const signed int *const END(shortest_path + n);
	while (iterator < END)
	{
	    *iterator = LONGEST_POSSIBLE_PATH;
	    ++iterator;
	}
	*availeable = true;
	*total_updates = 1;
	std::freopen("bellmanford.out","w",stdout);
	if (BellmanFord(n))
		std::printf("Ciclu negativ!");
	else
	{
	    iterator = shortest_path + 1;
		while (iterator < END)
		{
	    	std::printf("%d ",*iterator);
	    	++iterator;
	    }
	}
	std::printf("\n");
	std::fclose(stdout);
	return 0;
}