The day is cloudy and cheerful today , and so our little friend Zampa. Zampa loves this kind of weather and he feels to explore the city Opangya. The city is much beautiful and full of adventures. Creator of the city did architect it with most of Rose Gardens.
By the way it has been already a long time when the city was built. And by the time beautiful lovely Roses disappeared from the city one by one. And today there is no Rose.
Zampa wants to beautifies the city again with Roses. So today mission of our little Zampa is to bring Roses back. He will travel around the city on his feet to gather the Rose , if there is left any.
But Zampa does not know that few paths in city are full of Thorns which can hurt his feet. And he may need medical treatment to continue his journey , which in turn will cost him some money.
So Zampa needs your help to know that how much amount of money he should have to ensure that he will reach his destination and bring the Roses
Input : First line of input contains integer T number of Test-Cases. Next T lines will contain the following information. Integer N number of places where Rose may present.
Then lines will contain a b c integers till -1 is encountered where a represents source, b represents destination and c represents cost to travel from a to b.
Again next lines will have a b till -1 is encountered where a represents node and b represents another node and path a to b contains Thorns
Last input is floating value M which is rate rate of Medical treatment and the Medical treatment cost will be [M * (cost of path)].
Note : Graph is undirected. Zampa will not travel to any node again for any path. Medical treatment cost will be added extra with that path cost
Output : Output the path in given manner a1->a2->a3->....->an where a1...an are node for the path which will cost Maximum. Followed by the total cost of that path.
Cost should have two decimal after floating point.
For better explanation see Sample Case
Constraints
1<= T <= 10
3<= N <= 10
0.10<= M <= 0.80
Note : source node is always 0, and destination node will be (N-1)
Sample Input can be pictured as given in image below
Now the path with maximum Cost will be 1->2->7->6->3->5->8->9 with cost equal to 22.00
i.e. Cost for (path 1->2 = 2) + (path 2->7 = 4) + (extra for medical will be = [4 * 0.25] = 1) + (path 7->6 = 3) + (path 6->3 = 2) + (path 3->5 = 1) + (path 5->8 = 6) + (path 8->9 = 3) = 22.00
