小苯正处于一个 个点 条边的无向图内的 号节点上，他想要走到 号点去。图中的每条边都有一些边权 ，但这个花费非常奇怪。 具体的，小苯走到 号点的花费为：他经过的边里，权值最大的边的权 + 权值最小的边的权。 请你帮他求出他从 走到 号点的最短路是多少吧。

输入描述:

每个测试文件均包含多组测试数据。第一行输入一个整数  代表数据组数，每组测试数据描述如下：第一行两个正整数 ，分别表示图中的点数和边数。接下来 行，每行三个正整数 ，表示图中的每一条边。（保证所有测试数据中， 的总和不超过 ， 的总和不超过 。）

输出描述:

对于每组测试数据，在单独的一行输出一个整数，表示  号到 号点的最短路，如果不联通，输出 即可。