세계 일주

야체크는 세계를 한 바퀴 도는 비행을 하고 싶다. 돈이 넉넉하지 않아서 최대한 저렴하게 하려고 한다. 바이트항공의 항공편이 비교적 싸다는 것을 알아채고, 그들이 제공하는 모든 노선을 확인했다. 이제 지도를 펼쳐 놓고 계획을 짜는 중이다. 그를 도와주자!

야체크가 가진 자료는 도시 $n$개의 목록과 그 도시들 사이를 잇는 항공편 $m$개의 목록이다. 각 도시에 대해 야체크는 그 도시의 지리적 경도를 알고 있다. 각 항공편은 두 도시를 이으며 양방향 이동이 가능하다. 즉 도시 $a$에서 도시 $b$까지 $x$바이탈라로 갈 수 있다면, $b$에서 $a$로 가는 것도 가능하고 그 비용도 $x$바이탈라이다.

각 노선에 대해, 그 노선의 비행기가 서쪽으로 나는지 동쪽으로 나는지를 알고 있다 (어떤 두 도시도 같은 경도를 갖지 않는다고 가정한다). 각 비행기는 목적지까지 곧장 날아가며, 어떤 항공편도 극점 위를 지나거나 지구를 완전히 한 바퀴 돌지 않는다. 즉 한 항공편은 경도로 360도 미만을 지난다.

한 가지 문제가 남는다. "세계를 한 바퀴 돈다"는 것은 무슨 뜻일까? 야체크는 여행 전체에서 동쪽으로 비행한 경도의 총 도수가 서쪽으로 비행한 총 도수와 서로 달라야 한다고 정했다. 야체크는 자신의 고향인 1번 도시에서 여행을 시작하고 끝낼 계획이다.

다음 예시들을 살펴보자 (각 항공편은 항상 합리적인 방향, 즉 경도로 180도 미만을 지나는 방향으로 비행한다고 가정한다):

• 바르샤바 (21 E) - 모스크바 (37 E) - 도쿄 (139 E) - 로스앤젤레스 (118 W) - 뉴욕 (73 W) - 바르샤바 (21 E) 는 세계 일주 여행이다 (여행 내내 동쪽으로만 비행한다);
• 바르샤바 (21 E) - 모스크바 (37 E) - 도쿄 (139 E) - 로스앤젤레스 (118 W) - 마이애미 (80 W) - 카이로 (31 E) - 더블린 (6 W) - 바르샤바 (21 E) 도 세계 일주 여행이다 (동쪽으로는 합계 360도가 넘게, 서쪽으로는 카이로에서 더블린 구간에서만 비행한다);
• 바르샤바 (21 E) - 모스크바 (37 E) - 싱가포르 (103 E) - 로스앤젤레스 (118 W) - 마이애미 (80 W) - 카이로 (31 E) - 델리 (77 E) - 시드니 (151 E) - 부에노스아이레스 (58 W) - 요하네스버그 (28 E) - 바르샤바 (21 E) 는 세계 일주 여행이다 (동쪽으로는 720도가 넘게, 서쪽으로는 요하네스버그에서 바르샤바 구간에서 몇 도만 비행한다);
• 바르샤바 (21 E) - 모스크바 (37 E) - 싱가포르 (103 E) - 로스앤젤레스 (118 W) - 마이애미 (80 W) - 카이로 (31 E) - 요하네스버그 (28 E) - 부에노스아이레스 (58 W) - 시드니 (151 E) - 델리 (77 E) - 키이우 (30 E) - 바르샤바 (21 E) 는 세계 일주 여행이 아니다 (동쪽으로 비행한 도수가 서쪽으로 비행한 도수와 정확히 같다).

첫째 줄에는 두 정수 $n$과 $m$이 주어진다 ($2 \le n \le 100\,000$, $1 \le m \le 200\,000$). 각각 야체크의 지도에 있는 도시의 수와 바이트항공이 제공하는 항공편의 수를 뜻한다. 도시는 $1$부터 $n$까지 번호가 매겨져 있고, 야체크는 $1$번 도시에서 여행을 시작한다.

둘째 줄에는 각 도시의 좌표가 정수 수열 $w_1, \dots, w_n$으로 주어진다 ($0 \le w_i \le 1\,296\,000$). $w_i$는 $i$번 도시가 본초 자오선에서 동쪽으로 몇 지리적 초만큼 떨어져 있는지를 뜻한다 (1초는 $1/3600$도이다). 어떤 두 도시도 같은 경도를 갖지 않는다.

이어지는 $m$개의 줄은 각각 항공편 하나를 설명한다. $i$번째 줄에는 네 정수 $a_i$, $b_i$, $x_i$, $k_i$가 주어진다 ($1 \le a_i, b_i \le n$, $a_i \ne b_i$, $1 \le x_i \le 5\,000$, $k_i \in \{-1, 1\}$). 이는 바이트항공이 도시 $a_i$와 $b_i$ 사이를 $x_i$바이탈라에 운항하며, 도시 $a_i$에서 $b_i$로 가는 노선은 $k_i = 1$이면 동쪽으로, $k_i = -1$이면 서쪽으로 향한다는 뜻이다. 돌아오는 항공편은 반대 방향으로 향한다.

$1$번 도시에서 시작하고 끝나는 가장 저렴한 세계 일주 여행의 비용(바이탈라 단위)을 정수 하나로 출력한다. 그런 여행이 없으면 $-1$을 출력한다.