题目描述

简单来说，它要从标号为$\red{1}$的星球到标号为$\red{n}$的星球，某一些星球之间有航线。由于超时空隧道的存在，从一个星球到另一个星球时间可能会倒流，而且，从星球$\red{a}$到$\red{b}$耗费的时间和 星球$\red{b}$到$\red{a}$耗费的时间不一定相同。

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

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

输入格式

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

输出格式

输出文件共$\red{T}$行，每组数据输出一行。

如果可以通过调节速度调节器完成任务，则输出一个非负整数，表示由星球$\red{1}$到星球$\red{n}$的最短时间。（注意最短时间要大于或者等于$\red{0）}$。

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

样例

输入样例

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

输出样例

2

提示

把速度控制器的值设为$\red{1,}$相当于每个时间值加$\red{1,}$得到的最短路径为$\red{1→}$$\red{2→}$$\red{3→}$$\red{4,}$所需时间为$\red{2+(-2)+2=2}$。

$\red{1，}$$\red{2}$号测试点，保证所有星球出度不超过$\red{1}$

$\red{3，}$$\red{4}$号测试点，$\red{n<=10}$

$\red{5，}$$\red{6}$号测试点，$\red{-100<=t<=100}$

对于$\red{100\%}$的数据$\red{T<=10，}$$\red{n<=100，}$$\red{m<=n*(n-1)，}$$\red{-100000<=t<=100000}$

数据随机和构造结合生成