Water Slides

Inspired by the new water park at Machu Picchu in Peru, Farmer John has decided to build one for his cows. Its biggest attraction is a giant water slide of a peculiar design.

The superslide consists of $E$ mini slides connecting $V$ small pools, conveniently labeled $1$ through $V$. Every mini slide must be ridden in its proper direction and can never be traversed backwards. The cows start at pool $1$ and ride successive mini slides until they reach pool $V$, the final pool. Every pool except pool $1$ has at least one mini slide entering it, and every pool except pool $V$ has at least one mini slide leaving it.

Moreover, from any pool it is possible to reach pool $V$ by riding some sequence of mini slides. Finally, because this is a slide, once you leave a pool you can never return to it, no matter which mini slides you ride afterwards.

Each mini slide $i$ runs from pool $P_i$ to pool $Q_i$ ($P_i \ne Q_i$) and has a fun value $F_i$. Bessie's total fun on any trip down the superslide is the sum of the fun values of all the mini slides she rides.

Naturally Bessie wants to have as much fun as possible, so at each pool she normally chooses carefully which mini slide to take. However, she is a cow: at most $K$ times during her descent she loses control and is forced down an arbitrary mini slide leaving a pool — "arbitrary" meaning the worst possible one for her. This can even happen at pool $1$.

If Bessie plays so as to maximize her fun in the worst case, how much fun is she guaranteed to have on the given superslide?

Constraints: $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$.

For example, consider a small park with $3$ pools (pool numbers shown in brackets) and $4$ mini slides. Here $K = 1$, and each slide's fun value is shown outside the brackets:

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

Bessie always starts at pool $1$ and finishes at pool $3$. If she had her way, she would ride from pool $1$ to pool $2$ and then take the higher-fun slide (fun value $5$) to pool $3$, for a total of $5 + 5 = 10$. But if she loses control at pool $1$, she might slide straight from pool $1$ to pool $3$ for a total fun of $9$. If she loses control at pool $2$, her total fun could drop to $5 + 3 = 8$.

Because Bessie wants to guarantee as much fun as possible, she chooses to ride straight from pool $1$ to pool $3$ for a total of $9$. Even if she loses control at pool $1$ and is sent down the $1 \to 2$ slide, she has no losses of control left, so she will not lose control at pool $2$ and will end up with fun $10$. Thus she knows her guaranteed fun is always at least $9$.

• Line 1: three space-separated integers $V$, $E$, and $K$.
• Lines $2$ through $E + 1$: line $i + 1$ contains three space-separated integers $P_i$, $Q_i$, and $F_i$.

• A single line with one integer: the minimum fun Bessie can guarantee.