SP338 ROADS - Roads

题面描述 有标号为1……n的城市与单行道相连。对于每条道路有两个与之相关的参数：道路的长度以及需要支付的费用（用硬币的数量表示） 鲍勃和爱丽丝曾经生活在城市1。在注意到爱丽丝在他们喜欢玩的卡牌游戏中作弊后，鲍勃决定与爱丽丝分手并搬走——去城市n。他希望尽快到达那里——越快越好，然而他现在有些现金短缺。 我们希望帮助鲍勃找到从城市1到城市n的一条最短路径——但他必须用他现有的钱支付得起。

输入的第一行含有一个整数t代表测试样例的组数。下面是t组测试样例。 对于每组测试数据，第一行含有一个整数K（0

对于每组测试样例，输出单独的一行表示当花费小于等于K时最短路径的长度。如果不存在这样的路径，输出-1。