爆破检查

【题目描述】

祐树君和未奏希准备爆破王宫，他们准备好了炸弹，现在要对炸弹进行最后检查。

共有 $n$ 个炸弹，它们之间有 $m$ 条边相连，通过边所需的时间即为边的权值。

两人准备同时从 1 号节点出发，可以在到达任意节点后使用奥义·虚空遁地结束任务。两人的行动互不干扰，但在两人都结束任务之后要求每个节点至少被访问一次，此次任务所需时间为两人中后结束任务的那个所花的时间。

【输入格式】

第一行两个正整数 $n$ 、 $m$ ，表示节点数和边数。

接下来m行，每行三个正整数 $ui$ 、 $vi$ 、 $wi$ ，表示节点ui和 $vi$ 之间有一条权为 $wi$ 的双向边。

保证图联通且没有重边和自环。

【输出格式】

一行一个正整数，表示所需的最短时间。

【样例输入】

6 6

1 2 10

2 3 10

3 4 5

4 5 10

5 6 20

2 5 10

【样例输出】

【数据规模】

对于 50%的数据，1 ≤ $n$ ≤ 9。

对于 100%的数据，1 ≤ $n$ ≤ 18，1 ≤ $ui$ 、 $vi$ ≤ $n$ ，1 ≤ $wi$ ≤ 1000。

【时空限制】

1s，128MB

NOI.AC