该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

已知穗织镇是一个由 $n$ 个点和 $m$ 条边组成的无向图，[丛雨] 的家在 $1$ 号点，她现在想出去逛街。

然而当 丛雨 刚刚出门，一只魔物出现在了她后方，她想安全的回到家，但是她不能走回头路，因为会被魔物抓住，所以她想找一条尽量短的路，能够在不走回头路的情况下回到 $1$ 号点。

请你帮丛雨算一下，她最短需要走的路径长度是多少，如果丛雨无法安全回到家，输出 $-1$ 。

在本题中，不走回头路指的是不会有任意一条边经过 $2$ 次及以上。

输入格式

第一行，一个数整数 $T(1 \leq T \leq 10 )$ ，表示数据组数。

接下来 $T$ 组数据，每组数据开始为两个数正整数 $n, m(1 \leq n \leq 10000, 1 \leq m \leq 40000 )$ ，表示点和边的个数。

接下来 $m$ 行，每行三个正整数 $u, v, w(1 \leq w \leq 10^9)$ ，表示 $(u, v)$ 间有一条直接连接它们的长度为 $w$ 的边。

输出格式

输出 $T$ 行，每行一个整数，表示最短路径长度。

样例 1

输入

2
3 3
1 2 1
2 3 4
3 1 3
5 4
1 2 4
4 5 4
1 4 6
3 2 8

输出

8
-1

样例 2

见下发文件 burst2.in/out.

数据范围