워터 슬라이드

페루 마추픽추에 새로 생긴 워터파크에서 영감을 받은 농부 존은 소들을 위한 워터파크를 짓기로 했습니다. 이 워터파크의 최대 명물은 독특한 구조의 거대한 워터슬라이드입니다.

이 슈퍼슬라이드는 $1$번부터 $V$번까지 번호가 붙은 $V$개의 작은 수영장을 잇는 $E$개의 미니 슬라이드로 이루어져 있습니다. 모든 미니 슬라이드는 정해진 방향으로만 내려갈 수 있으며 거꾸로 올라갈 수는 없습니다. 소들은 $1$번 수영장에서 출발해 미니 슬라이드를 차례로 타고 내려가 마지막 수영장인 $V$번 수영장에 도착합니다. $1$번을 제외한 모든 수영장에는 들어오는 미니 슬라이드가 적어도 하나 있고, $V$번을 제외한 모든 수영장에는 나가는 미니 슬라이드가 적어도 하나 있습니다.

또한 어떤 수영장에서 출발하더라도 미니 슬라이드를 몇 개 타고 내려가면 반드시 $V$번 수영장에 도달할 수 있습니다. 그리고 슬라이드의 특성상, 한 수영장을 떠난 뒤에는 미니 슬라이드를 아무리 타더라도 그 수영장으로 다시 돌아올 수 없습니다.

각 미니 슬라이드 $i$는 수영장 $P_i$에서 수영장 $Q_i$로 이어지며($P_i \ne Q_i$), 재미 값 $F_i$를 가집니다. 베시가 한 번 슬라이드를 타고 내려가며 얻는 총 재미는 지나간 모든 미니 슬라이드의 재미 값의 합입니다.

베시는 당연히 최대한 재미있게 타고 싶어 합니다. 보통은 각 수영장에서 나가는 미니 슬라이드 중 무엇을 탈지 신중하게 고릅니다. 하지만 베시는 소이기 때문에, 내려가는 동안 최대 $K$번까지 제어를 잃고 어느 수영장에서 나가는 미니 슬라이드 하나를 임의로(즉, 자신에게 가장 불리한 것으로) 타게 됩니다. 이런 일은 $1$번 수영장에서도 일어날 수 있습니다.

베시가 최악의 경우에도 재미가 최대가 되도록 선택한다면, 주어진 슈퍼슬라이드에서 베시가 보장받을 수 있는 재미는 얼마일까요?

제약: $1 \le E \le 150{,}000$, $2 \le V \le 50{,}000$, $1 \le P_i \le V$, $1 \le Q_i \le V$, $0 \le F_i \le 2{,}000{,}000{,}000$, $1 \le K \le 10$.

예를 들어, 수영장 $3$개(대괄호 안이 수영장 번호)와 미니 슬라이드 $4$개로 이루어진 작은 공원을 생각해 봅시다. 여기서 $K = 1$이고, 각 슬라이드의 재미 값은 대괄호 밖에 적혀 있습니다.

          [1]
         /   \
   5 -> /     \ <- 9
       /       \
     [2]---3---[3]
        \__5__/

베시는 항상 $1$번 수영장에서 출발해 $3$번 수영장에서 끝납니다. 마음대로 할 수 있다면 $1$번에서 $2$번으로 내려간 뒤 재미가 더 큰 슬라이드(재미 값 $5$)를 타고 $3$번으로 내려가 총 $5 + 5 = 10$의 재미를 얻을 것입니다. 그러나 $1$번에서 제어를 잃으면 $1$번에서 곧장 $3$번으로 내려가 총 재미가 $9$가 될 수 있습니다. $2$번에서 제어를 잃으면 총 재미가 $5 + 3 = 8$로 줄어들 수 있습니다.

베시는 보장받는 재미를 최대로 만들고 싶으므로 $1$번에서 $3$번으로 곧장 내려가 총 재미 $9$를 택합니다. 만약 $1$번에서 제어를 잃어 $1 \to 2$ 슬라이드를 타게 되더라도, 남은 제어 상실 기회가 없으므로 $2$번에서는 제어를 잃지 않고 총 재미 $10$을 얻습니다. 따라서 베시는 자신이 보장받는 재미가 항상 $9$ 이상임을 알 수 있습니다.

워터 슬라이드

문제

입력

출력