Дан неориентированный связный граф, состоящий из \(n\) вершин и \(m\) ребер. \(k\) вершин этого графа — особенные.
Вы должны ориентировать каждое ребро графа (или оставить некоторые ребра неориентированными за дополнительную плату). Вы можете оставить \(i\)-е ребро неориентированным, заплатив \(w_i\) монет, или бесплатно ориентировать его.
Назовем вершину насыщенной, если она достижима из всех особенных вершин по ребрам графа (если ребро осталось неориентированным, по нему можно ходить в любом направлении). После того, как вы выберете направления для ребер графа (возможно, оставив некоторые неориентированными), вы получите \(c_i\) монет за каждую насыщенную вершину \(i\). То есть вашу итоговую прибыль можно посчитать по формуле \(\sum \limits_{i \in S} c_i - \sum \limits_{j \in U} w_j\), где \(S\) — множество насыщенных вершин, а \(U\) — множество ребер, оставшихся неориентированными.
Для каждой вершины \(i\) посчитайте максимальную прибыль, которую вы можете получить, если вы обязательно должны сделать вершину \(i\) насыщенной.
Выходные данные
Выведите \(n\) целых чисел, \(i\)-е из которых должно быть равно максимальной прибыли, которую вы можете получить, если необходимо сделать вершину \(i\) насыщенной.
Примечание
Рассмотрим первый пример:
- лучший способ насытить вершину \(1\) — направить ребра следующим образом: \(2 \to 1\), \(3 \to 2\); \(1\) — единственная насыщенная вершина, поэтому ответ равен \(11\);
- лучший способ насытить вершину \(2\) — оставить ребро \(1-2\) неориентированным, а другое ребро направить так: \(3 \to 2\); \(1\) и \(2\) — насыщенные вершины, стоимость ребра \(1-2\) равна \(10\), поэтому ответ равен \(2\);
- лучший способ насытить вершину \(3\) — направить ребра следующим образом: \(2 \to 3\), \(1 \to 2\); \(3\) — единственная насыщенная вершина, поэтому ответ равен \(5\).
Лучший план действий во втором примере — направить все ребра по циклу: \(1 \to 2\), \(2 \to 3\), \(3 \to 4\) и \(4 \to 1\). Таким образом, все вершины будут насыщенными.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
3 2 2
1 3
11 1 5
10 10
1 2
2 3
|
11 2 5
|
|
2
|
4 4 4
1 2 3 4
1 5 7 8
100 100 100 100
1 2
2 3
3 4
1 4
|
21 21 21 21
|