Description

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

Input

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

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

Output

  一个整数。Bessie选择了加倍某一条边的长度后，奶牛FJ从节点1到达节点N的最短路径是多少。但是输出的格式有变化，假设Bessie没有加倍某一条边的长度之前，FJ从1号节点到达N号节点的最短路径是X；在Bessie加倍某一条边的长度之后，FJ从1号节点到达N号节点的最短路径是Y，那么你输出的结果是Y-X。 

Sample Input

Sample Output

Hint

Source