问题 2658 --时间与空间之旅(tstrip)

2658: 时间与空间之旅(tstrip)

题目描述

  公元22××年,宇宙中最普遍的交通工具是spaceship。spaceship的出现使得星系之间的联系变得更为紧密,所以spaceship船长也成了最热门的职业之一。当然,要成为一名出色的船长,必须通过严格的考核,例如下面是最简单的问题中的一个。
用1~n的整数给n个星系标号,目前你在标号为1的星系,你需要送快递到标号为n的星系,星系之间由于存在陨石带,并不是都可以直连的。同时,由于超时空隧道的存在,在某些星系间飞行会出现时间静止甚至倒流,飞行时间为0或为负数。另外,由星系i到星系j的时间和由星系j到星系i的时间不一定是相同的。
在寄出日期之前收到快递被认为是不允许的,所以每部spaceship上都有一个速度调节装置,可以调节飞行的时间。简单来说其功能就是让所有两个星系间的飞行时间(如果可以直达)都增加或减少相同的整数值,你的任务就是调整速度调节器,找出一条用最短时间完成任务的路径,并且保证这个最短时间的值大于或等于0。

输入

输入文件包含多组数据,第1个数为T,表示数据的数量。
对于每一组数据,输入第1行为两个正整数N(2≤N≤100),E(1≤E≤N*(N-1)/2),为星系的个数和星系间飞行的路线数。然后E行,每行三个整数i,j和t(1≤i,j≤N,i≠j,-100000≤t≤100000),表示由星系i到星系j飞行的时间为t。由i到j最多只会有一条飞行线路。

输出

输出文件共T行,每组数据输出一行;
如果可以通过调节速度调节器完成任务,则输出一个非负整数,表示由星系1到星系N的最短时间。
如果不能由星系1到达星系N,则输出-1。

样例输入输出

输入#1 复制
1
4 5
1 2 1
1 3 1
2 3 -3
3 1 1
3 4 1
输出#1 复制
2

提示

样例说明
输入样例如图所示,其中节点标号表示相应星系,节点间数字表示所需时间。
如果设置速度控制器的值为0,则有如下路径:1→2→3→1→2→……→3→4,使得投递的时间为负无穷大,显然是不符合要求的,所以应该把速度控制器的值设为1,相当于每个时间值加1,得到的最短路径为1→2→3→4,所需时间为2+(-2)+2=2。


序号 标题 作者 发表时间 费用 订购数 操作