No testdata at current.

题目描述

你现在要从标号为 $1$的星球到标号为 $n$ 的星球。

某一些星球之间有航线，由于超时空隧道的存在，从一个星球到另一个星球时间可能会倒流，而且，从星球 $a$ 到 $b$ 耗费的时间和星球 $b$ 到 $a$ 耗费的时间不一定相同。

宇宙法规定：" 禁止在出发时间前到达目的地。"

每艘飞船上都有速度调节装置，可以调节飞行的时间。其功能可以使得整次航程中所有两星球间的飞行时间增加或减少相同的整数值。你的任务是帮助它调整速度调节器，找出一条最短时间到达目的地的路径。

输入格式

输入文件包含多组数据，第一个数为 $T$，表示数据组数。

对于每组数据，输入第一行为两个正整数 $n,m$，为星球的个数和星球间的路线数。接下来 $m$ 行，每行三个整数 $i,j$ 和 $t$，表示由星球 $i$ 到星球 $j$ 飞行的时间为 $T$。由 $i$ 到 $j$ 最多只会有一条飞行线路。

输出格式

输出文件共 $T$ 行，每组数据输出一行。

如果可以通过调节速度调节器完成任务，则输出一个非负整数，表示由星球 $1$ 到星球 $n$ 的最短时间。

如果不能由星球 $1$ 到达星球$n$ ，则输出 -1。

样例

样例输入

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

样例输出

2

样例解释：把速度控制器的值设为 $1$，相当于每个时间值加 $1$，得到的最短路径为$1\to 2\to 3\to 4$ ，所需时间为 $2+ \left ( -2 \right ) + 2 = 2$。

数据范围与提示

对于 $100\%$ 的数据，$1\le T\le 10，1\le n \le 100，1\le m\le n\ast \left ( n-1 \right ) ，-10^{6}\le t \le 10^{6}。$