时间限制：1秒　　内存限制：256M

---

【题目描述】

　　有 \(n\) 座星系，用 \(1 \sim n\) 的整数为每个星系标号，星系之间的交通工具是“太空飞船”。目前你在标号为 1 的星系，需要送快递到标号为 \(n\) 的星系。由于星系之间存在陨石带，所以并不是所有星系之间都可以直连。同时，由于时空隧道的存在，在某些星系之间飞行会出现时间静止甚至倒流，即可能出现两座星系之间飞行时间为 0 或为负数。另外，由星系 \(i\) 到星系 \(j\) 的时间和星系 \(j\) 到星系 \(i\) 的时间不一定相同。

　　在寄出日期之前收到快递被认为是不允许的，所以太空飞船上有一个速度调节器，可以调节飞行时间。简单地说其功能就是让所有可以直达星系之间飞行时间都增加或减少相同的数值，你的任务就是调整速度调节器，找出一条最短时间完成任务的路径，并且保证这个最短时间大于或等于 0。

【输入格式】

　　第一行为整数 \(T\)，表示数据组数。
　　每组数据第 1 行为整数 \(n,m\)，表示星系的数量和飞行路线数。然后的 \(m\) 行，每行 3 个整数：\(a,b,t\)，表示星系 \(i\) 到星系 \(j\) 的飞行时间为 \(t\)。\(i\) 到 \(j\) 最多只有一条飞行路线。

【输出格式】

　　输出 \(T\) 行，每组数据输出占一行。
　　如果可以通过速度调节器调节完成任务，则输出一个非负整数，表示星系 1 到星系 \(n\) 的最短时间，否则输出 -1。

【输入输出样例】

　Input

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

　Output

2

【输入输出样例解释】

　　样例的输入如下图所示：

　　如果设速度调节器的值为 0，则有如下路径：1->2->3->1->2->……->3->4，使得投递时间为负无穷大，显然不符合要求。所以应该把速度调节器的值设为 1，相当于每个时间值加 1，得到的最短路径为 1->2->3->4，所需要的最短时间为 2+(-2)+2=2。

【数据限制】

　　对于 \(100\%\) 的数据，\(2≤n≤100\)，\(1≤m≤n(n-1)/2\)，\(-100000≤t≤100000\)。

【来源】

　　Mr.he