409521: GYM103608 D Необычная ловушка

D. Необычная ловушкаограничение по времени на тест2 секундыограничение по памяти на тест256 мегабайтвводстандартный вводвыводстандартный вывод

Загадочник придумал новую ловушку для жителей Готэм–сити. По плану злодея, ловушка будет состоять из $$$n$$$ помещений, соединенных переходами так, чтобы из любого помещения $$$u$$$ всегда был единственный способ добраться в помещение $$$v$$$.

Для перемещения между комнатами нужно будет использовать специальный лифт, который может перемещаться по всем переходам ловушки. Одновременно лифт вмещает не больше $$$b$$$ людей, и когда лифт хотя бы с одним человеком внутри переезжает из помещения $$$u_i$$$ в помещение $$$v_i$$$, он теряет $$$w_i$$$ прочности. Лифт не теряет прочность, если в нем нет людей во время перемещения.

Загадочник планирует поделить всех своих жертв на $$$m$$$ групп так, чтобы в группе $$$i$$$ было $$$c_i$$$ человек, которые изначально находятся в комнате $$$x_i$$$, и обязаны добраться до комнаты $$$y_i$$$ (разумеется, используя лифт). При этом людям не запрещается временно высаживаться в произвольных местах пути и ждать перед тем, как продолжить движение.

Супер–злодей хочет выбрать такую прочность лифта, чтобы лифт мог доставить всех людей в нужные комнаты, но гарантированно разрушился (то есть его прочность упала до $$$0$$$) сразу после этого. Для этого он хочет найти минимальные возможные повреждения, которые может получить лифт, перемещая людей. Как опытный злодей, Загадочник справится с этой задачей, а справитесь ли вы?

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

В первой строке ввода через пробел даны три целых числа $$$n$$$, $$$m$$$ и $$$b$$$ — количество помещений в ловушке, количество групп людей и максимальная вместимость лифта ($$$2 \leqslant n \leqslant 10^5$$$; $$$1 \leqslant m \leqslant 2 \cdot 10^5$$$; $$$1 \leqslant b \leqslant 10^9$$$).

В следующих $$$n - 1$$$ строках дается описание комнат ловушки, между которыми есть переходы. В строчке $$$i$$$ даются три целых числа $$$u_i$$$, $$$v_i$$$ и $$$w_i$$$, означающие, что между комнатами $$$u_i$$$ и $$$v_i$$$ есть переход для лифта, наносящий лифту $$$w_i$$$ повреждений ($$$1 \leqslant u_i, v_i \leqslant n$$$; $$$0 \leqslant w_i \leqslant 10^4$$$). Гарантируется, что от любой комнаты можно добраться по переходам до любой другой.

В следующих $$$m$$$ строках дается описание групп людей. Описание группы номер $$$i$$$ — три целых числа $$$x_i$$$, $$$y_i$$$ и $$$c_i$$$ — номера стартовой и конечной комнат, и количество людей в группе ($$$1 \leqslant x_i, y_i \leqslant n$$$; $$$1 \leqslant c_i \leqslant 10^9$$$).

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

Выведите единственное число — минимальную величину повреждений, которые получит лифт после того, как все люди сбегут из ловушки Загадочника.

Система оценки

Баллы за каждую подзадачу начисляются только в случае, если все тесты этой подзадачи и необходимых подзадач, а также тесты из условия успешно пройдены.

Подзадача	Баллы	Дополнительные ограничения	Необходимые подзадачи	Информация о проверке
1	9	$$$n, m, b \leqslant 3$$$; $$$c_i \leqslant 3$$$ для всех $$$i$$$	–	полная
2	14	$$$n, m, b \leqslant 50$$$; $$$c_i \leqslant 50$$$ для всех $$$i$$$	1	полная
3	10	$$$n \leqslant 10^4$$$; $$$c_i \leqslant 10^4$$$ для всех $$$i$$$; $$$b = 10^9$$$	–	полная
4	16	каждое помещение соединено только с одним или двумя другими	–	полная
5	19	$$$n, m \leqslant 500 $$$	2	полная
6	12	$$$n \leqslant 5000 $$$	5	первая ошибка
7	20	нет	1 – 6	первая ошибка

ПримерыВходные данные

4 3 5
3 2 3
3 4 0
4 1 2
1 2 9
2 4 7
3 4 12

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

16

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

7 3 5
2 1 2
3 1 1
3 4 3
3 5 0
5 6 4
5 7 0
2 4 11
1 7 8
4 5 3

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

22

Примечание

В первом примере комнаты связаны по цепочке $$$2 \leftrightarrow 3 \leftrightarrow 4 \leftrightarrow 1$$$. Одна из возможных последовательностей действий выглядит так:

1. отвезти $$$5$$$ людей из второй комнаты в четвертую (потратив $$$3$$$ прочности);
2. вернуться во вторую, забрать $$$2$$$ человека из второй комнаты, и по пути в четвертую — подобрать еще $$$3$$$ человека в третьей (потратив $$$3$$$ прочности);
3. дальше доехать до первой, отвезти $$$5$$$ людей из нее во вторую (за $$$5$$$ прочности), и на обратном пути в первую подвести $$$5$$$ людей из третьей в четвертую (за $$$0$$$ прочности);
4. повторить последний шаг для оставшихся $$$4$$$ людей вместо $$$5$$$ (еще $$$5$$$ прочности).

Во втором примере один из оптимальных вариантов выглядит следующим образом: сначала доставить всех людей до комнаты номер $$$3$$$ (при чем люди, двигающиеся из комнаты номер $$$2$$$, должны будут взять себе попутчиков в комнате $$$1$$$), а после развести их по нужным комнатам в максимально возможных группах.