Вдохновлённый новым аквапарком в Machu Picchu в Перу, Farmer John решил построить свой для коров. Главный аттракцион — огромная водная горка необычной конструкции.

Она состоит из $E$ ($1 \le E \le 150,000$) малых горок, соединяющих $V$ ($2 \le V \le 50,000$) бассейнов $1..V$. По горке едут только в заданном направлении. Коровы начинают в 1 и едут до конечного $V$. В каждый бассейн, кроме 1, входит хотя бы одна горка, из каждого, кроме $V$, выходит хотя бы одна другая.

Из любого бассейна можно добраться до конца $V$. Нельзя выехать из бассейна и, проехав несколько горок, вернуться в него.

Горка $i$ ведёт из $P_{i}$ в $Q_{i}$ ($1 \le P_{i} \le V; 1 \le Q_{i} \le V; P_{i} \ne Q_{i}$) и имеет удовольствие $F_{i}$ ($0 \le F_{i} \le 2,000,000,000$). Общее удовольствие Bessie — сумма значений пройденных горок.

После долгого ожидания в очереди она хочет максимум удовольствия. Обычно выбирает выходы, но как корова не более $K$ раз ($1 \le K \le 10$) теряет контроль и едет по случайному выходу, даже из бассейна 1.

Какое удовольствие она гарантирует, выбирая оптимально для худшего случая?

Пример: 3 бассейна (номера в скобках), 4 горки, $K$ равно 1; удовольствие вне скобок:

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

Она идёт из 1 в 3. Свободно выбрала бы 1 в 2, затем горку с удовольствием 5 в 3: $5+5=10$. Потеря контроля в 1 может дать сразу 3 и 9, а в 2 — лишь $5+3 = 8$.

Она выбирает $1\to3$ для 9. Если в 1 потеряет контроль и уйдёт по $1\to2$, в 2 уже не потеряет и получит 10. Поэтому минимум всегда хотя бы 9.

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

• Строка $1$: три целых через пробел $V$, $E$, $K$.
• Строки $2..E + 1$: строка $i+1$ содержит три целых через пробел $P_{i}$, $Q_{i}$, $F_{i}$.

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

• Строка $1$: одно целое, минимальное удовольствие, которое Bessie гарантирует.

Примеры

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

3 4 1
2 3 5
1 2 5
1 3 9
2 3 3

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

9

Автор задачи: John Pardon, 2010