题目描述

有一个无向图，共N个节点，编号1至N，共M条边。FJ在节点1，它想到达节点N。FJ总是会选择最短路径到达节点N。作为捣蛋的奶牛Bessie，它想尽量延迟FJ到达节点N的时间，于是Bessie决定从M条边之中选择某一条边，使得改边的长度变成原来的两倍，由于智商的问题，Bessie不知道选择加倍哪条边的长度才能使得FJ到达N号节点的时间最迟。注意：不管Bessie选择加倍哪条边的长度，FJ总是会从1号节点开始走最短路径到达N号点。

输入格式

第一行，两个整数N和M. 1 <=N<=250, 1<=M<=250000。

接下来有M行，每行三个整数：A，B，L，表示节点A和节点B之间有一条长度为L的无向边。

1<=L<=1000000。

输出格式

一个整数。Bessie选择了加倍某一条边的长度后，奶牛FJ从节点1到达节点N的最短路径是多少。

但是输出的格式有变化，假设Bessie没有加倍某一条边的长度之前，FJ从1号节点到达N号节点的最短路径是X；

在Bessie加倍某一条边的长度之后，FJ从1号节点到达N号节点的最短路径是Y，那么你输出的结果是Y-X。

5 7
2 1 5
1 3 1
3 2 8
3 5 7
3 4 3
2 4 7
4 5 2

2

提示

把节点3到节点4的边从原来的长度3变成长度6

题目来源

Gold