小美想跑步
时间限制:C/C++/Rust/Pascal 1秒,其他语言2秒
空间限制:C/C++/Rust/Pascal 256 M,其他语言512 M
64bit IO Format: %lld

题目描述

暑假来了,对于小美来说,想要锻炼身体,游泳还不够,小美想:她还必须要跑步。

为此,小美在家的周围设置了 n-1 个打卡点,小美每次跑步都需要把这 n-1 个打卡点全部打卡。

但是小美喜欢轻装上阵,所以小美出去跑步时从来不带水杯。

可是小美又容易口渴,所以每次小美打卡完一个打卡点后,都要返回到家中去喝水。

小美第一次出去打卡是从家出发的,小美最后一次打完卡还要回到家中喝水。

况且小美很自律,所以她一定会出去打 n-1 次不同的卡,即便在打卡路上遇到了另一个打卡点,她也不会打卡。

不过小美想:既然已经在假期坚持游泳了,那么跑步上可不可以偷偷懒呢。

所以小美想请聪明的你来帮她想想办法,让她跑步的总路程最短。

输入描述:

输出描述:

输出一个整数,表示跑步的最短总路程。
示例1

输入

复制
4 6
1 2 2
2 4 4
1 4 1
4 3 2
3 1 5
1 3 3

输出

复制
29