미로 속 생쥐

작은 생쥐 한 마리가 거대한 미로에 갇혔습니다.

미로는 $n$개의 방으로 이루어져 있고, 방들은 $m$개의 복도로 연결되어 있습니다. 각 복도에는 폭이 정해져 있어서, 생쥐가 너무 뚱뚱하면 그 복도를 빠져나갈 수 없습니다.

몇몇 방에는 치즈 한 조각이 놓여 있습니다. 생쥐는 치즈가 있는 방에 들어가면 참지 못하고 그 조각을 통째로 먹어 버리며, 그만큼 몸이 두꺼워집니다. 몸이 두꺼워지면 일부 복도를 더 이상 지날 수 없게 될 수 있습니다.

생쥐의 몸 두께는 항상 "처음 두께 + 지금까지 먹은 치즈 무게의 합"과 같습니다. 폭이 $c$인 복도를 지나가려면 지날 때의 몸 두께가 $c$ 이하여야 합니다. 생쥐는 어떤 방에 처음 들어갈 때 그 방의 치즈를 먹으며, 출발하는 방 $s$에 있는 치즈도 처음부터 먹은 것으로 칩니다.

생쥐는 방 $s$에서 출발하고, 미로의 출구는 방 $d$입니다. 생쥐가 출구까지 나갈 수 있도록 하는 처음 두께의 최댓값을 구하세요. 처음 두께는 $0$ 이상이라고 가정합니다.

첫째 줄에 네 정수 $n$, $m$, $s$, $d$ ($1 \le n \le 10^6$, $1 \le m \le 2 \cdot 10^6$, $1 \le s, d \le n$, $s \ne d$)가 주어집니다. 각각 방의 수, 복도의 수, 생쥐가 출발하는 방, 출구인 방을 뜻합니다.

둘째 줄에 $n$개의 정수 $w_1, w_2, \dots, w_n$ ($0 \le w_i \le 10^9$)가 주어집니다. $w_i$는 생쥐가 $i$번 방의 치즈를 먹었을 때 두께가 얼마나 늘어나는지를 뜻하며, $w_i = 0$이면 그 방에는 치즈가 없습니다.

이어지는 $m$개의 줄에 각 복도의 정보가 한 줄씩 주어집니다. 각 줄에는 세 정수 $a$, $b$, $c$ ($1 \le a, b \le n$, $1 \le c \le 10^9$)가 있으며, 이 복도가 방 $a$와 방 $b$를 연결하고 생쥐의 두께가 최대 $c$일 때에만 지날 수 있음을 뜻합니다.

생쥐가 미로에서 빠져나갈 수 있는 처음 두께의 최댓값을 정수 하나로 출력합니다. 처음 두께가 $0$이어도 빠져나갈 수 없다면 $-1$을 출력합니다.