28626번 - Необычная ловушка 다국어

Загадочник придумал новую ловушку для жителей Готэм--сити. По плану злодея, ловушка будет состоять из $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$).

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

В первом примере комнаты связаны по цепочке $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$), а после развести их по нужным комнатам в максимально возможных группах.