Background

Description

Format

Input

Output

Sample

Input

4 4 2
1 2 12
1 3 8
2 4 12
3 4 18

Output

6

Limitation

1s, 128000KiB for each test case.

Hint

Source

CDQZ TEST