萌新求助，如题： 网上找不到答案，第一眼看上去像是先求mst再树形dp，但不会证明该题所求的方案一定是最小生成树的一部分，感觉跟局部最小生成树之类的东西有关但同样搜不到相关资料，题目来自某个网上找的学案

[Discription]

一个国家有n个城市，有m条双向道路将这些城市连接使得这些城市直接都能直接或间接地连通，每条道路连接两个不同的城市，每条道路都有一个通畅度。在这n个城市中有1个城市是首都。现打算建立一个以首都为中心，共由k个城市(包括首都且k ≤ n)组成的城市群，选取k个城市，选择并开发连接这k个城市的若干条道路作为城市群的主干道，开发之后每条主干道的通畅度变为原来的2倍。由于建设经费有限，只够开发刚刚好能使k个城市互相连通的数量的主干道，这些主干道开发后的通畅度的总和即为该城市群的通畅度。在满足上述条件的情况下，请选择一种方案使该城市群的通畅度最大化，并求出这个值。

[Input]

第一行3个整数：n, m, k 接下来m行每行3个整数u, v, p，表示编号为u的城市和编号为v的城市间有一条双向道路，该道路通畅度为p，保证城市编号最大不超过n

[Output]

共1行，一个整数ans表示城市群的通畅度的最大值

[Data size and conventions]

对于20%的数据，n, m ≤ 100，1 ≤ k ≤ n 对于另外20%的数据，n, m ≤ 10000，k = n 对于另外20%的数据，n, m ≤ 100000，1 ≤ k ≤ 100 对于100%的数据，n, m ≤ 100000，1 ≤ k ≤ n