图上极差 II

友情提示：补题是一个好习惯，本题与图上极差 I 唯一的区别在于扩大了 $n$ 和 $m$ 的范围到 $10^5$，并且将时间限制改为 3000ms。此外，图上极差 I 的评测数据是本题评测数据的子集，占 $50\%$。

题目描述

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

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

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

输入格式

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

数据范围

$1 \le n \le 100000$

$1 \le m \le 100000$

$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