由于员工都富裕起来了，大家都买了车，然后上班的时候公司门口都停满了车，乱七八糟的。所以，公司今天发布了一个通告，通告是这样说的：
现在规定公司门口只能停k辆车，但是为了避免大家争议到底谁可以停公司门口，现在公司决定给所有人都定好。
我们按以下步骤走：
1.把你们家之间的距离都告诉我。
2.我们要节约能源，所以所有人都开到公司来的话，太浪费能源了。
3.你们之间可以停在路过的同事的家里然后坐同事的车一起过来。
快快快，快告诉我怎么规划他们的停车问题使得耗费的能源最少。
先规定车可以容纳无数人，同事的家里可以停无数辆车子。

公司编号为0。

第一行输入两个数N (3 <= N <= 30) 和M (N - 1 <= M <= N * (N - 1) / 2)。N表示该公司有N个员工(编号为1到N)，M表示所有员工汇报给公司的路线数量。
接下来有M行，每行有三个整数x，y (0 <= x, y <= 30 && x != y)，和 z (0 < x < 100)，表示员工x家与员工y家之间的驾驶车辆要耗费z元钱的油费。
最后输入一个数 k (1 <= k <= 10)，表示公司门口最多只能停k辆车。
向你保证所有小于等于出现的最大的编号都会出现，即不存在独立的点。

当所有员工都到达公司时，输出满足条件的最小费用。