夹道之樱
时间限制：C/C++/Rust/Pascal 1秒，其他语言2秒
空间限制：C/C++/Rust/Pascal 256 M，其他语言512 M
64bit IO Format: %lld

题目描述

我们就此开始一起攀登那条漫长的、樱花盛放的坡道。
在一座山上，有n个亭子，连接这这n个亭子的，是m条可以双向行走的步道。每条步道的两旁都栽种着两行樱花树，然而由于光照、土质和打理频率差异，每条步道的美观程度并不一样，第i条步道连接着亭子ai和亭子bi，美观程度为ci。
现在我们想从1号亭子前往n号亭子，并且由于不希望景色出现太大差异，我们希望经过的步道的美观度的最大值和最小值的差尽可能小。请你求出这个最小值。

点击下载大样例

输入描述:

第一行两个整数n,m，代表亭子和步道的数量。
接下来m行，每行3个整数ai,bi,ci，代表该步道两端的亭子编号和这条步道的美观度。

输出描述:

共一个整数，代表在最优方案中，经过步道的美观度的最大值和最小值的差的最小值。
示例1

输入

复制 
4 4
1 2 1
2 4 4
1 3 3
3 4 2

输出

复制 
1

说明

从亭子1到亭子n，共有两条路径：
1→2→4，经过步道的美观度最大值为4，最小值为1，差值为3；
1→3→4，经过步道的美观度最大值为3，最小值为2，差值为1；
因此最小的差值为1。

备注:

数据范围：
对于30%的数据，有；
对于60%的数据，有；
对于100%的数据，有；

保证给定的图是个连通图，但可能有重边或自环。