A102289.雾港城的道路网

雾港城的道路网是一张无向带权图。每个路口 $i$ 都有一个“标高” $h[i]$。
你要从起点 $S$ 走到终点 $T$，路径的总代价为经过道路长度之和。

但夜里巡逻有规定：一路上标高只能 先不下降、再不上升（允许相等）。
也就是说，存在某个位置（可以在起点或终点），使得整条路径的标高序列满足：

• 前半段：标高单调不下降；
• 后半段：标高单调不上升；

中途只允许发生一次“从上升到下降”的大转折（不转折也算合法）。

请你求出满足规定的最短路长度；若不存在合法路径输出 $-1$。

第一行四个整数 $n,m,S,T$，表示点数、边数、起点、终点。
第二行 $n$ 个整数 $h[1],h[2],\dots,h[n]$。
接下来 $m$ 行，每行三个整数 $u,v,w$，表示一条无向边 $(u,v)$，边权为 $w$。

输出一个整数，表示最短合法路径长度；若无解输出 $-1$。

样例解释

解释：若直接走 1-2-5-6，标高为 1,3,2,1，中间先上升再下降，合法，代价为 $2+1+2=5$。
而 1-2-3-4-5-6 的标高 1,3,5,4,2,1 也是“先不降后不上”，代价更大。
所以答案为 $5$。

数据范围与测试点

• $1\le n\le200000$
• $0\le m\le200000$
• $1\le w\le10^9$
• $1\le h[i]\le10^9$

测试点编号	$n$ 上界
$1\sim4$	$n\le20$
$5\sim10$	$n\le10000$
$11\sim20$	$n\le200000$