돌다리 놓기

다현이와 정연이는 섬 $N$개로 이루어진 여울 마을에 산다. 정연이는 가장 서쪽 섬에, 다현이는 가장 동쪽 섬에 산다. 두 사람은 섬마다 $1$번부터 $N$번까지 번호를 붙였고, 정연이가 사는 섬이 $1$번, 다현이가 사는 섬이 $N$번이다.

배를 타고 서로의 섬을 오가기가 불편해서, 두 사람은 $3$번 섬에 사는 건축가 성열이에게 섬 $N$개를 잇는 돌다리를 놓아 달라고 부탁했다.

성열이는 돌다리 $M$개를 놓기로 계획을 세웠다. $M$개를 모두 놓으면 섬 $N$개가 하나로 연결된다. 돌다리끼리는 중간에서 겹치지 않고, 양 끝의 두 섬을 빼면 다른 섬을 지나지도 않는다. $k$번 돌다리를 놓는 데는 $T_k$의 시간이 걸린다.

성열이는 돌다리를 한 번에 하나씩, 아무 순서로나 놓는다. 돌다리를 놓다 보면 $1$번 섬과 $N$번 섬을 돌다리로 오갈 수 있게 되는 순간이 온다. 그 순간까지 흐른 시간은 그때까지 놓은 돌다리의 건설 시간을 모두 더한 값이다.

위 그림과 같은 마을을 생각해 보자. 성열이가 번호 순서대로 $1, 2, \dots, 9$번 돌다리를 놓으면, 여섯 개를 놓은 시점인 $17$ 단위 시간 뒤에 $1$번 섬과 $N$번 섬이 이어진다. $1$번 돌다리와 $6$번 돌다리를 차례로 놓으면 $6$ 단위 시간 만에 이어진다. 어떤 순서로 놓아도 $5$ 단위 시간 안에는 $1$번 섬에서 $N$번 섬으로 갈 수 없다. 한편 $1, 9, 7, 5, 8, 3, 2, 6, 4$번 순서로 놓으면 여섯 개를 놓은 시점인 $22$ 단위 시간이 지나서야 이어지고, 어떤 순서로 놓아도 $22$ 단위 시간이 지난 뒤에는 반드시 $1$번 섬에서 $N$번 섬으로 갈 수 있다.

섬과 돌다리 정보가 주어질 때, $1$번 섬과 $N$번 섬이 이어지는 시점의 최솟값과 최댓값을 구하는 프로그램을 작성하여라.

첫째 줄에 섬의 수 $N$이 주어진다. ($4 \le N \le 50000$)

다음 $N$개의 줄에는 각 섬의 좌표 $X_k$와 $Y_k$가 주어진다. ($1 \le X_k, Y_k \le 1000000$, $X_1 < X_k < X_N$)

그 다음 줄에는 성열이가 놓으려는 돌다리의 수 $M$이 주어진다. ($N - 1 \le M \le 1000000$)

다음 $M$개의 줄에는 $k$번 돌다리가 잇는 두 섬의 번호 $S_k$와 $E_k$, 그리고 건설 시간 $T_k$가 주어진다. ($S_k \ne E_k$, $1 \le T_k \le 10000$)

$1$번 섬을 빼면 $x$좌표가 $X_1$ 이하인 섬은 없고, $N$번 섬을 빼면 $x$좌표가 $X_N$ 이상인 섬도 없다. 위치가 완전히 같은 두 섬은 없다. 또 어떤 두 섬을 잇는 돌다리는 많아야 한 개다.

첫째 줄에 $1$번 섬과 $N$번 섬이 이어지는 시점의 최솟값과 최댓값을 공백으로 구분해 출력한다.