An oligarch Vovan, as many other oligarchs, transports oil from West Cuckooland
to East Cuckooland. He owns a huge oilproducing station in West Cuckooland,
an equally huge oilrefining station in East Cuckooland and a system of oil
pipelines to move oil from one country to another. Vovan has a map of these
pipelines on his table. He would like to know, how much oil this system can
transport.
Each pipeline connects some pair of stations. All stations on the map are numbered: the producing station has number 1, the refining one has number N and the transit ones have numbers from 2 to N − 1, inclusive. Each pipeline can transport a limited quantity of oil, but in any direction. Vovan doesn't know that the Earth is round, so each station on his map has plane coordinates (x_{i} and y_{i} are the coordinates of ith station). The pipelines are represented as line segments. Any pair of pipelines on the map can intersect only at endpoints. It is known, that the oilproducing station has the smallest xcoordinate of all stations, and the oilrefining station has the largest xcoordinate.
Input
The first line contains an integer N. 2 ≤ N ≤ 10000. Next N lines
contain the coordinates of the stations (x_{i}, y_{i}) separated with a space.
Coordinates are integers with absolute values no more than 10^{8}. Next line
contains an integer M — the number of oil pipelines. Next M lines contain specifications of pipelines: for each pipeline, the three numbers describe a pair of stations connected by it and its flow capacity — an integer from 1 to 10^{8}. It is guaranteed that Vovan's system can transport some positive quantity of oil, and can't transport more than 2·10^{9} oil units.
Output
In the first line output the maximal quantity of oil that the Vovan's system
can transport. In the following M lines output the transportation plan — triples of numbers (A, B, C), denoting that C oil units should flow from station A to station B. All pipelines should be presented exactly once in this list (even those, in which the oil flow is equal to zero). The values of C should always be nonnegative.
Sample
input  output 

3
0 0
1 1
2 0
2
1 2 2
2 3 1
 1
1 2 1
2 3 1

Problem Author: Artem Melentyev
Problem Source: Ural SU Contest. Petrozavodsk Winter Session, January 2008