flood

In 2005, Romania was under water. Hundreds of bridges fell, hundreds of roads were destroyed.
The Prime Minister set up an emergency situation council, analyzing the country map. The map has marked on it N important localities. The localities are numbered from 1 to N. We also have marked on the map the existing roads between localities that can be traveled on, but also the roads that have been destroyed. The estimated cost for road rebuilding is also specified for every destroyed road.
The Prime Minister wishes to build a minimum number of roads, so that in the end there be a connection between the N localities marked on the map. If there is more than one solution with a minimum number of roads, the one for which the sum of rebuilding costs is smallest will be preferred.

Task

Determine the roads that have to be rebuilt, as well as the minimum amount of money spent on rebuilding.

Input Data

Input file flood.in contains on line one a positive integer N, representing the number of localities.
Line two contains a non-negative integer M, which represents the number of existing roads that can be traveled.
Each of the following M lines contain two positive integers each, X and Y, between 1 and N, separated by a space, with the meaning that "between localities X and Y there is a road that can be traveled".
The next line contains a non-negative integer P, representing the number of destroyed roads.
Each of the following P lines contain three positive integers, each separated by a space, X, Y and C, with the meaning that "rebuilding the road between X and Y costs C RON".

Output Data

Output file flood.out will contain on line one a non-negative integer nr, representing the minimum number of roads that have to be rebuilt. The second line will contain a non-negative integer S representing the sum of rebuilding costs for the nr roads (minimum possible). Each of the following nr lines will contain three positive integers each separated by a space, X Y C, with the meaning that "the road between X and Y of cost C will be rebuilt".

Constraints and Statements

• 0 < N <= 10 000
• 0 <= M, P <= 200 000
• The rebuilding costs are non-zero positive integers <= 1000
• Roads between localities are two-directional.
• There can be more than one connecting roads between two localities.
• Total rebuilding costs do not exceed 2 000 000 000.
• Before the floods there was a connection between any two localities.
• Partial scores will be given as follows:
  - for correctly determining the minimum number of roads, 20% of the test score;
  - for correctly determining the minimum number of roads and minimum, 50% of the test score;
  
  

Time limit: 0.6 seconds/test

prof. Emanuela Cerchez
"Grigore Moisil" Iaşi IT High School
Contact:emanuela.cerchez@gmail.com