Travel Plan

All submissions for this problem are available.
XYZ is an International Airline Company. It has flights between different cities across the globe but does not have a direct flight for all the pairs of cities. Flights are such that, all the cities with an airport are reachable by other city either by a direct flight or through other cities. Total number of flights is of the order of number of airports.
For the past few years, their statistics are given below:
 2005  487 flights covering 319 different airports.
 2007  782 flights covering 549 different airports.
 2009  1197 flights covering 886 different airports.
They are planning to start a new flight between cities x and y, whose cost would be C units for the passengers. They need to calculate the percentage decrease in the total minimum cost for all pair of cities. So, let say total minimum cost to travel between all pairs of cities is initially C1 and after the new flight introduction becomes C2. You need to calculate (C1C2)X100/C1.
Input
First line would give t (number of test cases).
Each test case starts with line containing n(number of cities) and f(number of flights) seperated by space.
All the cities are numbered as 0,1,2,...,n1.
Next f lines will give, index of two cities(i and j) and the cost of flight(C).
Each case ends with a line containing x and y with its cost separated by space.
t<=10
n<=1000, f<=2000
C<=30000 units (is always an integer)
Output
For each test case output the percentage decrease rounded off to two decimal places on a separate line.
Example
Input: 2 3 2 0 1 3500 1 2 4000 0 2 2700 5 7 0 1 5500 2 3 8100 4 0 4300 1 2 2300 0 3 6000 4 2 3100 3 4 3700 1 3 2800 Output: 32.00 14.93
Author:  manthan 
Tags  manthan 
Date Added:  26032010 
Time Limit:  0.728261 sec 
Source Limit:  50000 Bytes 
Languages:  C, CPP14, GO, NODEJS, PYP3 
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. 