Masonry Bridge

Dahyun and Jeongyeon live in Yeoul village, which has $N$ islands. Jeongyeon lives on the westernmost island and Dahyun lives on the easternmost one. They numbered the islands from $1$ to $N$, giving number $1$ to Jeongyeon's island and number $N$ to Dahyun's island.

Rowing a boat between the two islands is inconvenient, so they asked Seongyeol, an architect who lives on island $3$, to build masonry bridges that connect the $N$ islands.

Seongyeol planned to build $M$ bridges. Once all $M$ bridges are built, the $N$ islands form one connected group. No two bridges overlap anywhere in the middle, and no bridge passes through an island other than the two at its ends. Building bridge $k$ takes $T_k$ units of time.

Seongyeol builds the bridges one at a time, in an arbitrary order. At some moment during the construction, Dahyun and Jeongyeon can cross between their islands over the bridges. The time elapsed at that moment is the sum of the construction times of the bridges built so far.

Consider the village in the picture above. If Seongyeol builds the bridges in index order $1, 2, \dots, 9$, islands $1$ and $N$ become connected after six bridges, which is $17$ units of time. If he builds bridge $1$ and then bridge $6$, they become connected after $6$ units of time. No order connects them within $5$ units of time. If he builds the bridges in the order $1, 9, 7, 5, 8, 3, 2, 6, 4$, they become connected only after six bridges, which is $22$ units of time, and once $22$ units of time have passed islands $1$ and $N$ are connected whatever order he used.

Given the islands and the bridges, write a program that finds the smallest and the largest possible moment at which islands $1$ and $N$ become connected.

The first line contains the number of islands $N$ ($4 \le N \le 50000$).

Each of the next $N$ lines contains the coordinates $X_k$ and $Y_k$ of one island ($1 \le X_k, Y_k \le 1000000$, $X_1 < X_k < X_N$).

The next line contains the number of bridges $M$ that Seongyeol plans to build ($N - 1 \le M \le 1000000$).

Each of the next $M$ lines contains the numbers $S_k$ and $E_k$ of the two islands that bridge $k$ connects, and its construction time $T_k$ ($S_k \ne E_k$, $1 \le T_k \le 10000$).

Apart from island $1$, no island has an $x$ coordinate at most $X_1$, and apart from island $N$, no island has an $x$ coordinate at least $X_N$. No two islands sit at exactly the same position. At most one bridge connects any pair of islands.

Print the smallest and the largest possible moment at which islands $1$ and $N$ become connected, separated by a space.