暂无测试数据。

大样例：https://paste.ubuntu.com/p/kXPkTjCTyH/

输出：62

已知兰德索尔是一个由 $n$ 个点和 $m$ 条边组成的无向图，Kyaru 的家在 $1$ 号点，她现在想出去逛街。

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

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

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

输入格式

第一行，一个数 $T$，表示数据组数。 

 接下来 $T$ 组数据，每组数据开始为两个数 $n,m$，表示点和边的个数。 

 接下来 $m$ 行，每行 $3$ 个数 $u,v,w$，表示 $(u,v)$ 间有一条直接连接它们的长度为 $w$ 的边。

输出格式

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

数据规模与约定

对于 $20\%$ 的数据，$1 \leq n \leq 5, 1 \leq m \leq 5$;

对于 $50\%$ 的数据，$1 \leq n \leq 100,1 \leq m \leq 100$;

对于 $100\%$ 的数据，$1 \leq n \leq 10000,1 \leq m \leq 40000,1 \leq w_{ij} \leq 10^9,1\leq T \leq 10$。

保证没有重边和自环。

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