#BT04. 夜行班车

夜行班车

题目描述

有 nn 个站点和 mm 条双向道路。第 ii 条道路的高度为 wiw_i,班车只能通过高度不超过自身通行等级的道路。 求从站点 ss 到站点 tt 所需的最低通行等级。若始终无法到达,输出 -1。 道路可以重边,每条道路的两个端点不同。

输入格式

第一行四个整数 n,m,s,tn,m,s,t。接下来 mm 行,每行 ui,vi,wiu_i,v_i,w_i。

输出格式

一个整数,表示最低通行等级或 -1。

数据范围

2≤n≤2000002\le n\le200000,0≤m≤3000000\le m\le300000,1≤s,t,ui,vi≤n1\le s,t,u_i,v_i\le n,s≠ts\ne t,ui≠viu_i\ne v_i,1≤wi≤1091\le w_i\le10^9。

样例 1

4 4 1 4
1 2 8
2 4 1
1 3 5
3 4 5
5

解释

经过 1,3,41,3,4,最高道路高度为 55。

样例 2

3 1 1 3
1 2 7
-1