슈가 글라이더

슈가 글라이더 JOI가 살고 있는 숲에는 유칼리 나무가 $N$그루 있고, 1부터 $N$까지 번호가 붙어 있다. 나무 $i$의 높이는 $H_i$미터이다.

JOI는 서로 직접 날아갈 수 있는 나무 쌍이 $M$개 있고, 각 쌍을 오가는 데 걸리는 시간이 정해져 있다. 나무 사이를 날아갈 때는 매 초 지면에서 1미터 높이가 줄어든다. 현재 높이가 $h$미터이고 이동에 $t$초가 걸리면, 도착 높이는 $h-t$미터이다. $h-t$가 0 미만이거나 목적 나무 높이보다 크면 날아갈 수 없다.

JOI는 나무 옆면을 오내려 지면에서 0미터부터 현재 나무 높이까지 높이를 바꿀 수 있다. 높이를 1미터 바꾸는 데 1초가 걸린다.

JOI는 나무 1의 높이 $X$미터 지점에서 나무 $N$ 꼭대기(높이 $H_N$)로 가려 한다. 걸리는 최소 시간을 구하는 프로그램을 작성한다.

표준 입력에서 읽는다.

• 1행: 정수 $N$, $M$, $X$ (나무 수, 직접 이동 가능한 쌍 수, 시작 높이)
• 다음 $N$행: 나무 $i$의 높이 $H_i$
• 다음 $M$행: $A_j$, $B_j$, $T_j$ (나무 $A_j$와 $B_j$를 $T_j$초로 오갈 수 있음)

나무 1 높이 $X$에서 나무 $N$ 꼭대기까지 가는 최소 시간(초)을 한 줄에 출력한다. 불가능하면 $-1$을 출력한다.

• $2 \le N \le 100\,000$
• $1 \le M \le 300\,000$
• $1 \le H_i \le 1\,000\,000\,000$
• $1 \le T_j \le 1\,000\,000\,000$
• $0 \le X \le H_1$