有一片由 座城市组成的王国。城市的编号从 到 （含两端）且有 条道路连接各个城市。对于任意两座城市，居民们都可以沿着这些道路互相访问。
皇后最近决定建设 座新的工厂。为了防止污染，她规定每座城市最多只能建立一座工厂。
您作为皇家设计师，需要在规划建设的同时，求出两两工厂之间距离之和的最大值。
两座工厂之间的距离，即为两座工厂所在的两座城市之间的最短路径长度。路径的长度即为路径中所有边的长度之和。
每个测试文件仅有一组测试数据。
第一行输入两个整数 和 （，）表示城市的数量与新建工厂的数量。
对于接下来 行，第 行输入三个整数 ， 和 （，，）表示有一条道路连接城市 与 ，其长度为 。
输出一行一个整数表示两两工厂之间距离之和的最大值。
6 3 1 2 3 2 3 2 2 4 1 1 5 2 5 6 3
22
样例数据解释如下。
:::align{center} :::
可以选择在城市 ， 和 建立工厂。令 表示城市 与 之间的最短路径长度，则答案为 。
:::