Lấy cảm hứng từ công viên nước mới ở Machu Picchu tại Peru, Farmer John xây một công viên cho bò. Điểm thu hút lớn nhất là máng trượt nước khổng lồ thiết kế kỳ lạ.

Có $E$ máng nhỏ ($1 \le E \le 150,000$) nối $V$ hồ nhỏ ($2 \le V \le 50,000$), đánh số $1..V$. Chỉ đi theo chiều đúng, không ngược. Bò đi từ 1 qua các máng tới hồ cuối $V$. Mọi hồ trừ 1 có ít nhất một máng vào, trừ $V$ có ít nhất một máng khác đi ra.

Từ mọi hồ đều tới cuối $V$ được. Không thể rời một hồ rồi qua các máng và trở lại hồ đó.

Máng $i$ từ $P_{i}$ tới $Q_{i}$ ($1 \le P_{i} \le V; 1 \le Q_{i} \le V; P_{i} \ne Q_{i}$), có niềm vui $F_{i}$ ($0 \le F_{i} \le 2,000,000,000$). Tổng niềm vui của Bessie là tổng các giá trị máng đã qua.

Đợi xếp hàng lâu nên cô muốn vui nhất. Thường chọn kỹ lối ra, nhưng là bò nên tối đa $K$ lần ($1 \le K \le 10$) mất kiểm soát và theo lối ngẫu nhiên, kể cả ở 1.

Nếu chọn để tối đa niềm vui trong trường hợp xấu nhất, cô bảo đảm bao nhiêu?

Ví dụ 3 hồ, số hiệu trong ngoặc vuông, 4 máng và $K$ bằng 1; niềm vui ngoài ngoặc:

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

Luôn từ 1 tới 3. Tự chọn sẽ đi 1 tới 2 rồi máng vui hơn giá trị 5 tới 3: $5+5=10$. Mất kiểm soát ở 1 có thể đi thẳng tới 3 được 9, ở 2 chỉ $5+3 = 8$.

Cô chọn $1\to3$ được 9. Nếu mất kiểm soát ở 1 rồi đi $1\to2$, cô không mất ở 2 nữa và được 10. Do đó đảm bảo ít nhất 9.

Dữ liệu vào

• Dòng $1$: số nguyên $V$, $E$, $K$ cách nhau bằng dấu cách.
• Dòng $2..E + 1$: dòng $i+1$ chứa số nguyên $P_{i}$, $Q_{i}$, $F_{i}$ cách nhau bằng dấu cách.

Dữ liệu ra

• Dòng $1$: một số nguyên, niềm vui tối thiểu Bessie bảo đảm.

Ví dụ

Dữ liệu vào 1

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

Dữ liệu ra 1

9

Tác giả bài toán: John Pardon, 2010