你的朋友，疯子 Tommy Vercetti，遇到了麻烦。他劫持了一辆救护车，必须将散落在罪恶都市（Vice City）各处的病人运送到当地医院。他想尽快完成这项任务，以便继续执行其他任务（主要是涉及暴力犯罪的任务）。因此，你必须编写一个计算机程序，计算完成该任务所需的最短时间。

救护车最多可容纳三名病人。救护车需要返回医院以放下病人。罪恶都市由街道和交叉路口组成。其中一个交叉路口是医院所在地，其他每个交叉路口都有一名病人需要接走。每条街道都是双向的，并关联有一个成本，即从一端行驶到另一端所需的分钟数。救护车的装载和卸载是瞬间完成的。在每个场景开始时，救护车都在医院。

输入格式

输入的第一行包含一个整数 $T$，表示测试用例的数量。 每个测试用例的第一行包含两个整数 $N$ 和 $M$，分别表示包含病人的交叉路口数量和双向街道的数量。接下来的 $M$ 行包含三个整数 $a_i, b_i, c_i$。这些行中的每一行代表交叉路口 $a_i$ 和 $b_i$ 之间的一条双向街道，$c_i$ 是从 $a_i$ 到 $b_i$（或反方向）行驶所需的分钟数。罪恶都市共有 $N + 1$ 个交叉路口，编号为 $0$ 到 $N$（包含 $0$ 和 $N$）。医院位于交叉路口 $N$，病人们位于交叉路口 $0, 1, \dots, N - 1$。

输出格式

对于每个测试用例，输出将所有病人送往医院所需的最短分钟数。

说明

• $0 < T \le 100$
• $1 \le N \le 20$
• $M > 0$
• $0 \le a_i, b_i \le N$
• $0 < c_i \le 100000$
• 任意两个交叉路口之间总是存在路径。
• 任意两个交叉路口之间不存在两条或多条街道。

样例

输入 1

1
2 2
0 1 10
1 2 10

输出 1

40