图上极差

题目描述

update(25/04/06)本题数据已经加强。

Orange正在学习图论算法，他将给定你一张 $n$ 个点，$m$ 条边的带权无向图，现在他打算从 $S$ 点走到 $T$ 点，且要求最小化所经过边的极差。请你帮他求出最小的极差。

注意：你可以重复经过一条边多次！

经过边的极差定义为经过的最大边权与最小边权之差。

输入格式

第一行为4个整数 $n,m,S,T$，表示图的点数和边数，以及起点和终点。 接下来 $m$ 行，每行3个整数 $u,v,w$，表示点 $u$ 和 $v$ 之间存在一条长度为 $w$ 的边。

数据范围

$1 \le n \le 2000$ $1 \le m \le 5000$ $1 \le w \le 10^9$ 数据保证图联通。

输出格式

输出一个整数，表示答案。

样例 #1

样例输入 #1

5 5 1 5
1 2 1
2 4 2
4 5 4
1 3 7
3 5 9

样例输出 #1

2