왕복 여행

짐(Jim)은 산악 지역의 어느 마을에 사는 가장 친한 친구를 만나러 가려고 한다. 그는 먼저 고향을 떠나 목적지 마을로 가는데, 이를 가는 여정(go)이라 한다. 그런 다음 고향으로 돌아오는데, 이를 오는 여정(return)이라 한다. 이 여행 전체의 최소 비용을 구하는 프로그램을 작성하라. 전체 비용은 가는 여정의 비용과 오는 여정의 비용의 합이다.

마을들은 고향과 목적지를 포함하는 하나의 도로망을 이룬다. 모든 도로는 일방통행이며, 정해진 방향으로만 지날 수 있다. 도로를 지날 때마다 정해진 비용이 든다.

도로 비용 외에도, 지나는 각 마을에서는 비자 요금을 내야 한다. 이는 비자 요금이므로 같은 마을을 처음 방문할 때만 내면 되고, 두 번째 이후의 방문에는 요금이 들지 않는다.

각 마을에는 고도가 있다. 가는 여정에서는 내려갈 수 없다. 즉 마을 $a$에서 $b$로 이동할 때 $a$의 고도가 $b$의 고도보다 높으면 안 된다. 오는 여정에서는 반대로 올라갈 수 없다. 즉 $a$의 고도가 $b$의 고도보다 낮으면 안 된다. $a$와 $b$의 고도가 같으면 도로 $a \to b$는 두 여정 모두에서 사용할 수 있다.

입력은 여러 개의 데이터셋으로 이루어진다. 각 데이터셋의 형식은 다음과 같다.

n m
d2 e2
d3 e3
...
d(n-1) e(n-1)
a1 b1 c1
a2 b2 c2
...
am bm cm

모든 값은 음이 아닌 정수이며, 한 줄 안의 값들은 공백 하나로 구분된다.

$n$은 마을의 수, $m$은 일방통행 도로의 수이며 $2 \le n \le 50$, $0 \le m \le n(n-1)$이다. 마을은 $1$번부터 $n$번까지 번호가 매겨진다. $1$번 마을이 고향, $n$번 마을이 목적지이다.

$2 \le i \le n-1$인 각 마을 $i$에 대해 $d_i$는 비자 요금, $e_i$는 고도이며 $1 \le d_i \le 1000$, $1 \le e_i \le 999$이다. $1$번과 $n$번 마을은 비자 요금이 없다. $1$번 마을의 고도는 $0$, $n$번 마을의 고도는 $1000$이다. 여러 마을이 같은 고도를 가질 수 있으나, 하나의 고도를 공유하는 마을은 최대 $10$개이다.

$j$번째 도로는 마을 $a_j$에서 $b_j$로 이어지며 비용은 $c_j$이고, $1 \le a_j \le n$, $1 \le b_j \le n$, $1 \le c_j \le 1000$이다. $a_j$에서 $b_j$로는 갈 수 있지만, 별도의 도로가 주어지지 않는 한 $b_j$에서 $a_j$로는 갈 수 없다. 서로 다른 두 도로가 같은 (출발, 도착) 쌍을 갖지 않으며, 자기 자신으로 이어지는 도로도 없다.

마지막 데이터셋 다음에는 공백으로 구분된 두 개의 $0$이 담긴 줄이 온다. 이 줄은 처리 대상이 아니다.

각 데이터셋에 대해, 비자 요금을 포함한 여행의 최소 총비용을 한 줄에 출력한다. 유효한 여행이 존재하지 않으면 $-1$을 출력한다.