A New Russian Kolyan wants an oil delivery to foreign partners to become his main source of income. His company owns a number of pumping stations with network of pipelines connecting them. First, Kolyan wants to increase the amount of the transferred oil by 1 million barrels per day. Help Kolyan to achieve this goal spending the minimal amount of money.

The first line contains an integer N, which is the number of pumping stations between which there are pipelines (1 ≤ N ≤ 10000). The stations are numbered from 1 to N. The next N lines describe the stations.

The i^th line contains quadruples of integers a b c d (1 ≤ a ≤ N; 0 ≤ c ≤ b ≤ 10000; 0 ≤ d ≤ 10⁶), where
a is the number of a station to which a pipeline from the station i exists,
b is the flow capacity of the pipeline from i to a in millions of barrels per day,
c is the present oil flow from i to a in millions of barrels per day,
d is the amount of money (in roubles) necessary for the increase in the flow capacity of the pipeline from i to a by 1 million barrels per day. There can be at most 1 pipeline from station i to station a and no pipeline connects a station with itself.

These quadruples in the line are separated with commas, and there is a period after the last quadruple. If oil is not transported anywhere from the i^th station, then the corresponding line contains only one symbol ".". It is guaranteed that there are no more than 100000 quadruples describing pipelines in the input.

Oil is transferred to foreign partners at only one pumping station with the number N. The cross-border oil flow is equal to the incoming flow at this station. From this station, oil is not transported to other pumping stations in the described pipeline network. Pumping stations with numbers less than N are transit stations. It is known that for each transit station the incoming oil flow is not more than the outgoing flow. If the incoming flow is less than the outgoing flow, then there is an oil-producing well nearby, whose oil production can easily be increased by 1 million barrels per day.

In the first line output the minimal cost K of reconstructing the pipeline network in such a way that the oil transfer to foreign partners is increased by 1 million barrels per day. Then output N lines describing the oil flow in the pipelines after the reconstruction, in the following format: the i^th of these lines must contain a list of pairs a b separated with commas; a is the number of a station to which oil is transported from the station i, and b is the number of the transported oil in millions of barrels per day. Each of these lines must end with a period.

If it's impossible to reach Kolyan's goal then output single word "Impossible".