暂无测试数据。

Description

给你一个包含 \(n\) 个顶点 \(m\) 条边有向图， 顶点编号 \(1\) 到 \(n\)。因为是有向图，所以从顶点 \(a\) 到顶点 \(b\) 的边的长度值和从顶点 \(b\) 到顶点 \(a\) 的边的长度值不一定相同。
你有一种特殊操作，可以使得所有两个顶点间边的长度减少或增加一个相同的整数值，你的任务是通过这种特殊操作，找出一条从顶点 \(1\) 到顶点 \(n\) 的最短路径。注意：最短路径必须要大于或者等于 \(0\)。

Input

输入包含多组数据，第 \(1\) 个数为 \(T\)，表示数据组数。
每组数据的输入第 \(1\) 行为两个正整数 \(n\)，\(m\)，为顶点数和边数。
接下来 \(m\) 行，每行三个整数 \(u\)，\(v\) 和 \(w\)，表示由顶点 \(u\) 到顶点 \(v\) 的边的长度为 \(w\)，\(u\) 到 \(v\) 最多只会有一条边。

Output

输出共 \(T\) 行，每组数据输出一行。
如果可以通过特殊操作完成任务，则输出一个非负整数，表示从顶点 \(1\) 到顶点 \(n\) 的最短路径长度，如果不能由顶点 \(1\) 到达顶点 \(n\)，则输出 \(-1\)。

Sample

Sample Input

1
4 5
1 2 1
1 3 1
2 3 -3
3 1 1
3 4 1

Sample Output

2

Sample Explanation

特殊操作可以把每条边的长度值都加 \(1\)，得到最短路径为 \(1\rightarrow 2\rightarrow 3\rightarrow 4\)，得到 \(1\) 到 \(4\) 的最短长度为 \(2+(-2)+2=2\)。

Hint

对于所有数据：\(T\leq 10\)，\(n\leq 100\)，\(m\leq n(n-1)\)，\(-100000\leq w\leq 100000\)。