Maximum Induced Subgraph Weight

You are given an undirected weighted graph \(G=(V,E)\) with \(N\) vertices and \(M\) edges. Each edge \((a_i,b_i,w_i)\) represents a relationship between person \(a_i\) and person \(b_i\) with a positive intimacy level \(w_i>0\).

Your task is to choose exactly \(K\) vertices \((K \leq N)\) to maximize the sum of the weights of all edges whose both endpoints are in the selected set \(S\). Formally, you need to select \(S \subseteq V\) such that \(|S| = K\) and maximize the following objective:

[ \sum_{(a_i,b_i,w_i)\in E \wedge a_i \in S \wedge b_i \in S} w_i ]

Note: The graph is undirected; each relationship appears only once but can be considered in both directions.

inputFormat

The first line contains three integers \(N\), \(M\), and \(K\).

Then \(M\) lines follow, each containing three numbers \(a_i\), \(b_i\), and \(w_i\) indicating an edge between vertices \(a_i\) and \(b_i\) with weight \(w_i\).

You may assume that \(1 \leq a_i, b_i \leq N\) and \(w_i > 0\). It is guaranteed that \(K \leq N\).

outputFormat

Output a single integer representing the maximum possible sum of edge weights among any set of exactly \(K\) vertices.

sample

4 4 2
1 2 1
1 3 2
2 4 3
3 4 4

4