题目描述

。 接下来 m 行，每行三个整数 u,v,w，表示有一条大道连接区 u 和区 v，且拥挤度为 w。 两个区之间可能存在多条大道。

输入格式

第一行有四个用空格隔开的 n，m，s，t，其含义见

输出格式

输出一行一个整数，代表最大的拥挤度。

样例

输入样例 1

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

输出样例 1

2

输入样例 2

4 4 1 3
1 2 1
2 3 2
1 4 2
4 3 3

输出样例 2

2

输入样例 3

2 1 1 2
1 2 5

输出样例 3

5

提示

数据规模：1≤n≤10^4，1≤m≤2×10^4，w≤10^4，1≤s,t≤n。且从 s 出发一定能到达 t 区 。

思路：题目是求从起点可达终点的所有经过路径中最长的一段边权的最小值。 Kruskal最小生成树： 将边从小到大排序，然后克鲁斯卡尔最小生成树连边，这样当S和T第一次连通时，当前边的权值就是答案了。