#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];

bool BellmanFord (unsigned int n)
{
	unsigned short node, neighbor;
	signed int distance, new_distance;
	bool not_updated;
	struct list_element *iterator;
	for (unsigned short updates(1) ; updates < n ; ++updates)
	{
		not_updated = true;
		for (node = 0 ; node < n ; ++node)
		{
	    	if (availeable[node])
	    	{
	    		availeable[node] = false;
	    		distance = shortest_path[node];
	    		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;
	    				availeable[neighbor] = true;
	    				not_updated = false;
	    			}
	    		}
	    	}
		}
		if (not_updated)
		    return false;
	}
	for (node = 0 ; node < n ; ++node)
		if (availeable[node])
			for (iterator = graph[node] ; iterator ; iterator = iterator->next)
				if (shortest_path[node] + iterator->node.path < shortest_path[iterator->node.number])
					return true;
	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, *node1_adress(&node1), *node2_adress(&node2);
	signed short path, *path_adress(&path);
	struct list_element *new_element;
	do
	{
		std::scanf("%hu%hu%hd",node1_adress,node2_adress,path_adress);
		--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;
	std::freopen("bellmanford.out","w",stdout);
	if (BellmanFord(n))
		std::printf("Ciclu infinit!");
	else
	{
	    iterator = shortest_path + 1;
		while (iterator < END)
		{
	    	std::printf("%d ",*iterator);
	    	++iterator;
	    }
	}
	std::printf("\n");
	std::fclose(stdout);
	return 0;
}