32635번 - $A_i+A_j$

문제

1ドル$번부터 $N$번 정점까지 총 $N$개의 정점과 $M$개의 가중치가 있는 단방향 간선으로 이루어진 그래프가 주어진다. 다음 조건을 만족하는 정수 쌍 $(i,j)$ 중에서 $A_i +A_j$의 최솟값을 구해보자.

• 1ドル\leq i \lt j \leq N$
• $S$에서 출발하고 $T$에 도착하는 최단 경로 중에서, $i$번 정점과 $j$번 정점을 동시에 지나는 경우가 존재한다.

$S$에서 출발하고 $T$에 도달하는 최단 경로는 하나가 아닐 수도 있음에 유의하자. 심지어 존재하지 않을 수도 있다.

최단 경로가 존재하지 않거나 조건을 만족하는 정수 쌍 $(i,j)$가 존재하지 않는 경우에는 -1을 출력하자.

입력

첫째 줄에 정점의 개수를 나타내는 정수 $N$과 간선의 개수를 나타내는 정수 $M$이 공백을 사이에 두고 주어진다. $(2 \leq N, M \leq 10^6)$

둘째 줄에 정수로 이루어진 수열 $A_1, A_2, \dots, A_N$이 공백을 사이에 두고 주어진다. $(1 \leq A_i \leq 10^6)$

셋째 줄에 출발 정점의 번호 $S$와 도착 정점의 번호 $T$가 공백을 사이에 두고 주어진다. $(1\leq S, T \leq N, S \neq T)$

넷째 줄부터 $M$개의 줄에 걸쳐 간선을 나타내는 세 정수 $u,ドル $v,ドル $c$가 공백을 사이에 두고 주어진다. $(1 \leq u, v \leq N, u \neq v, 1 \leq c \leq 10^6)$

이는 $u$번 정점에서 출발해 $v$번 정점에 도달하는 거리 $c$의 단방향 간선을 의미한다.

출력

최단 경로가 존재하지 않거나 조건을 만족하는 정수 쌍 $(i,j)$가 존재하지 않는다면 첫째 줄에 -1을 출력한다.

존재한다면, 첫째 줄에 정답을 출력한다.

제한

힌트