Дан ориентированный ацикличный граф (ориентированный граф, не содержащий циклов) из \(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\) целых чисел \(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\).
Примеры
| № | Входные данные | Выходные данные |
|
1
|
3 2
2 1 4
1 3 2
|
1 2 0
|
|
2
|
5 4
1 2 1
2 3 1
1 3 6
4 5 8
|
43 42 41 1337 1336
|
|
3
|
5 5
1 2 1
2 3 1
3 4 1
1 5 1
5 4 10
|
4 3 2 1 2
|