题目描述

一座城市有 $n$ 个街区和 $m$ 条道路，每条道路连接两个街区并有一个拥挤度。小明的妈妈需要从街区 $s$ 前往街区 $t$，她希望选择一条路线，使得路线上最拥挤的那条道路的拥挤度尽可能小。

请帮她求出这条最优路线上最大拥挤度的最小值。

输入格式

第一行四个整数 $n, m, s, t$，用空格隔开。

接下来 $m$ 行，每行三个整数 $u, v, w$，表示有一条道路连接街区 $u$ 和街区 $v$，拥挤度为 $w$。

两个街区之间可能存在多条道路。

输出格式

输出一行一个整数，表示最优路线上最大拥挤度的最小值。

样例

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

2

提示

数据规模与约定

• 对于 $30\%$ 的数据，保证 $n \leq 10$。
• 对于 $60\%$ 的数据，保证 $n \leq 100$。
• 对于 $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$。