K-th Minimum Spanning Tree

You are given a connected, undirected, weighted graph without self-loops and multiple edges. Your task is to compute the weight of the kth minimum spanning tree.

• The weight of a spanning tree is defined as the sum of the weights of its edges.
• Two spanning trees are considered different if and only if there exists an edge that is in one spanning tree but not in the other.
• If the kth spanning tree does not exist, output -1.

Note: It is assumed that the graph is small enough to allow a brute force enumeration of all spanning trees.

inputFormat

The first line of input contains three integers n, m and k where:

• n is the number of vertices.
• m is the number of edges.
• k denotes the kth minimum spanning tree to find.

Each of the next m lines contains three integers u, v and w, representing an edge between vertices u and v with weight w.

outputFormat

Output a single integer representing the weight of the kth minimum spanning tree. If there is no kth spanning tree, output -1.

sample

3 3 1
1 2 1
2 3 2
1 3 3

3