G. Очередное взвешивание графа
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
1024 мегабайта
ввод
стандартный ввод
вывод
стандартный вывод

Дан ориентированный ацикличный граф (ориентированный граф, не содержащий циклов) из $$$n$$$ вершин и $$$m$$$ дуг. $$$i$$$-я дуга ведет из вершины $$$x_i$$$ в вершину $$$y_i$$$ и имеет вес $$$w_i$$$.

Ваша задача — для каждой вершины $$$v$$$ выбрать некоторое целое число $$$a_v$$$, после чего на каждой дуге $$$i$$$ записать такое число $$$b_i$$$, что $$$b_i = a_{x_i} - a_{y_i}$$$. Вы должны выбрать числа таким образом, чтобы:

  • все $$$b_i$$$ были положительны;
  • значение выражения $$$\sum \limits_{i = 1}^{m} w_i b_i$$$ было минимально возможным.

Можно показать, что для любого ориентированного ацикличного графа с неотрицательными $$$w_i$$$ такой способ выбрать числа существует.

Входные данные

В первой строке заданы два целых числа $$$n$$$ и $$$m$$$ ($$$2 \le n \le 18$$$; $$$0 \le m \le \dfrac{n(n - 1)}{2}$$$).

Далее следуют $$$m$$$ строк, $$$i$$$-я из них содержит три целых числа $$$x_i$$$, $$$y_i$$$ и $$$w_i$$$ ($$$1 \le x_i, y_i \le n$$$, $$$1 \le w_i \le 10^5$$$, $$$x_i \ne y_i$$$) — описание $$$i$$$-й дуги.

Гарантируется, что строки задают описание $$$m$$$ дуг ориентированного ацикличного графа без кратных дуг.

Выходные данные

Выведите $$$n$$$ целых чисел $$$a_1$$$, $$$a_2$$$, ..., $$$a_n$$$ ($$$0 \le a_v \le 10^9$$$), которые необходимо записать на вершинах, чтобы все $$$b_i$$$ были положительны, и значение выражения $$$\sum \limits_{i = 1}^{m} w_i b_i$$$ было минимально возможным. Если ответов несколько — выведите любой. Можно показать, что ответ всегда существует, и хотя бы один из оптимальных ответов удовлетворяет ограничениям $$$0 \le a_v \le 10^9$$$.

Примеры
Входные данные
3 2
2 1 4
1 3 2
Выходные данные
1 2 0
Входные данные
5 4
1 2 1
2 3 1
1 3 6
4 5 8
Выходные данные
43 42 41 1337 1336
Входные данные
5 5
1 2 1
2 3 1
3 4 1
1 5 1
5 4 10
Выходные данные
4 3 2 1 2