Friends Meeting

All submissions for this problem are available.
Read problems statements in Mandarin Chinese, Russian and Vietnamese as well.
Chef and his friend John have not see each other for years. They are both are looking forward to meeting again in the city they both grew up in.
The city has N public squares that they can meet in. The squares are numbered from 1 to N and are connected with N1 roads. Each road has its own length
It is known that between two squares there is exactly one path that goes through the roads and squares such that no square appears in the path more than once. Roads do not intersect each other and it takes 0 time to pass through a square.
Chef and John have previously met in squares A_{1}, A_{2}, ..., A_{M} so they will meet in one of these squares again. To make this meeting more adventurous they do not agree on the square beforehand. Rather, Chef will pick a random square C from this list of squares and John will independently pick a random square J from this list of squares. Both random choices will be taken uniformly over the list of squares.
In the day before the meeting, Chef spoke with his roomate about their plan and asked him to calculate the expected distance between squares that Chef and John randomly pick. Please remember that Chef's roommate knows neither C nor J. Help him calculate this expected distance.
Input
The first line of the input contains an integer T denoting the number of test cases. The description of T test cases follows.
The first line of each test case contains two spaceseparated integers N and M.
The next N1 lines contain three spaceseparated integers V, U, and L describing a road with length L between squares V and U.
The final line of each case contains M spaceseparated integers A_{1}, A_{2}, ..., A_{M}.
Output
For each test case, output a single line containing two integers numer and denom separated by a space. These indicate the fraction numer/denom giving expected distance between the squares randomly chosen by Chef and John. This fraction should be reduced so that gcd(numer, denom) = 1 and denom ≥ 1.
Constraints
 1 ≤ T ≤ 5
 1 ≤ N ≤ 50000
 1 ≤ M ≤ N
 1 ≤ V ≤ N
 1 ≤ U ≤ N
 1 ≤ L ≤ 10000
 1 ≤ A_{i} ≤ N
 The squares A_{i} are distinct.
 Subtask #1 [40 points]: N ≤ 1000
 Subtask #2 [60 points]: No additional constraints
Example
Input: 2 6 2 1 3 1 2 3 2 3 4 3 4 5 4 4 6 5 1 5 6 6 1 3 1 2 3 2 3 4 3 4 5 4 4 6 5 1 2 3 4 5 6 Output: 4 1 29 6
Author:  cenadar 
Tester:  xcwgf666 
Editorial  http://discuss.codechef.com/problems/FRIEMEET 
Tags  cenadar, dfs, medium, nov16, tree 
Date Added:  29072015 
Time Limit:  1 sec 
Source Limit:  50000 Bytes 
Languages:  C, CPP14, JAVA, PYTH, PYTH 3.5, PYPY, CS2, PAS fpc, PAS gpc, RUBY, PHP, GO, NODEJS, HASK, SCALA, D, PERL, FORT, WSPC, ADA, CAML, ICK, BF, ASM, CLPS, PRLG, ICON, SCM qobi, PIKE, ST, NICE, LUA, BASH, NEM, LISP sbcl, LISP clisp, SCM guile, JS, ERL, TCL, PERL6, TEXT, SCM chicken, CLOJ, FS 
Comments
 Please login at the top to post a comment.
SUCCESSFUL SUBMISSIONS
Fetching successful submissions
HELP
If you are still having problems, see a sample solution here. 