Description

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

Format

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。

Samples

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

2

Limitation

INPUT DETAILS: There are 5 fields and 7 pathways. Currently, the shortest path from the house (field 1) to the barn (field 5) is 1-3-4-5 of total length 1+3+2=6. （把节点3到节点4的边从原来的长度3变成长度6）