说明

小明所在的城镇有$m$条路连接了$n$个区（$n$个区的编号在1~$n$的范围内），每条大道将两个区相连接，每条大道有一个拥挤度。小明想要开车从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≤10$

对于 60% 的数据，保证$n≤100$

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