Migrated from Lutece 1636 梦后楼台高锁，酒醒帘幕低垂

All parts of this problem, including description, images, samples, data and checker, might be broken. If you find bugs in this problem, please contact the admins.

Description

给你一个有$n$个点和$m$条边的无向连通图,每条边都有一个权值$w$.
我们定义，对于一条路径，它的Charm value为该路径上所有边的权值的最大值与最小值的差.
询问从$1$到$n$的所有路径的Charm value的最小值.

Input

第一行有两个整数$n,m\left ( 1\leq n\leq 200,n - 1\leq m\leq 1000 \right )$，表示该图有$n$个点和$m$条边.
接下来$m$行，每行三个整数$u,v,w\left ( 1\leq u,v\leq n,1\leq w\leq 1000000 \right )$，表示点$u$和点$v$之间有一条权值为$w$的边.

Output

输出一个数，即从$1$到$n$的所有路径的Charm value的最小值.

Samples

4 4
3 4 1
2 3 2
1 2 4
2 4 3

1

Resources

2017 UESTC Training for Graph Theory