问题描述

妈妈下班回家后得知，小明被一群陌生人带到了编号为 $t$ 的区域，而妈妈自己位于编号为 $s$ 的区域。

城市中共有 $n$ 个区域和 $m$ 条双向道路，每条道路连接两个区域，并具有一个拥挤度。

妈妈希望从 $s$ 走到 $t$，同时尽量避免经过过于拥挤的道路。因此，请你规划一条路线，使得整条路线中经过道路的最大拥挤度尽可能小。

求这个最小可能的最大拥挤度。

输入格式

第一行包含四个整数 $n,m,s,t$，分别表示区域数量、道路数量、起点和终点。

接下来 $m$ 行，每行包含三个整数 $u,v,w$，表示区域 $u$ 与区域 $v$ 之间有一条双向道路，其拥挤度为 $w$。

保证从 $s$ 出发一定能够到达 $t$。

输出格式

输出一个整数，表示从 $s$ 到 $t$ 的所有路径中，路径上最大拥挤度的最小值。

样例输入

3 3 1 3
1 2 2
2 3 1
1 3 3

样例输出

2

说明

从区域 $1$ 到区域 $3$ 有两种主要路线：

• $1 \rightarrow 3$，路径上的最大拥挤度为 $3$；
• $1 \rightarrow 2 \rightarrow 3$，路径上的最大拥挤度为 $\max(2,1)=2$。

因此最优方案为第二条路线，答案为 $2$。

评测数据规模

对于 $100\%$ 的数据：保证 $1 \leq n\leq 10^4$，$1 \leq m \leq 2 \times 10^4$，$w \leq 10^4$，$1 \leq s, t \leq n$。且从 $s$ 出发一定能到达 $t$ 区。

且保证从 $s$ 到 $t$ 至少存在一条路径。