Oil pipelines
Oligarch Vovan, like many other oligarchs, is engaged in transporting oil from Western Kukulandia to Eastern Kukulandia. He owns a large oil extraction station in Western Kukulandia, a similarly large oil refining station in Eastern Kukulandia, and a network of pipelines that transfer oil between the two regions. On Vovan's desk is a map of these pipelines, and it would be interesting to determine how many units of oil this system can transport.
Each pipeline connects a specific pair of stations. On the map, all stations are numbered: the extraction station is numbered 1, the refining station is numbered N, and the transit stations are numbered from 2 to N-1. Each pipeline has a limited capacity for transporting oil, but it can carry oil in either direction. Vovan is unaware that the Earth is round, so each station on his map has flat coordinates (x_i and y_i - coordinates of the i-th station). Pipelines are represented as straight line segments. On the map, pipelines can only intersect at a common station-vertex. It is known that among all stations, the extraction station has the smallest x coordinate, and the refining station has the largest x coordinate.
Input
The first line contains the number N - the number of stations on the map (2 ≤ N ≤ 10000). The next N lines provide the coordinates of the stations (x_i, y_i) separated by a space. The coordinates are integers that do not exceed 10^8 in absolute value. The following line contains an integer M - the number of pipelines. Then, in the next M lines, the details of the pipelines are given - a pair of station numbers connected by the pipeline, along with the pipeline's capacity in units - an integer from 1 to 10^8. It is guaranteed that the pipeline system can transport a non-zero amount of oil, but cannot transport more than 2·10^9 units of oil.
Output
On the first line, output the maximum number of units of oil that Vovan's system can transport. In the following M lines, provide the transportation plan - triples of numbers (A, B, C), indicating that C units of oil should flow from station A to station B. Each pipeline must be represented in this list exactly once (even those through which no oil flows). The number C in all triples must be non-negative.