Split the network into regions

Problem

A company has n offices and m possible two-way cables "a b w" with price w. All offices can be connected using the cables. The company wants exactly K separate regions: offices inside a region are connected, but there is no cable between regions. Print the smallest total price of the cables to buy.

Input, output and limits

Input: Line 1: n and m. Next m lines: a, b and w. Last line: K.
Output: One integer.
Constraints: 1 ≤ K ≤ n ≤ 1000
n - 1 ≤ m ≤ 2500
1 ≤ w ≤ 1000000
All offices can be connected

Examples

Example

Input

Output

Connect everything for 13, then leave out the cable of price 9.

Hints

Try the problem first. Open one hint at a time.

Hint 1

Run Kruskal: it adds the cheapest cables first and every added cable lowers the number of regions by one.

Hint 2

Stop as soon as exactly K regions are left.

Write your Python code, run it on the examples and submit it to hidden tests.

Solve in the editor

All Python problems

Problem

Input, output and limits

Examples

Hints

More Graph Algorithms problems

Problem

Input, output and limits

Examples

Hints

More Graph Algorithms problems