D. Random walks in Thailand
time limit per test
3.5 seconds
memory limit per test
64 megabytes
input
standard input
output
standard output

Thailand is made up of a few hundred islands. In each reasonably-sized island there is an airport used by small aircraft. However, the transport system seems quite peculiar for visitors...

Ferry boats are very reliable. For instance, you can depart from Ko Khang Khao (เกาะคางคาว) and get to neighbouring islands for a reasonable price using ferry boats: Ko Sichang (เกาะสชง), Ko Kham Yai (เกาะขามใหญ), Ko Kham Noi (เกาะขามนอย), Ko Ram Dok Mai (เกาะรามดอกไม), Ko Prong (เกาะปรง)}, or Ko Yai Thao (เกาะใหญทาว) (Yes, Ko means island in Thai).

The airplane pilots, on the other hand, are very erratic. Once you pay the flight fare, the pilot will drop you off at a random island, each with the same probability, including the one you departed from. Even though the destination of the flight is random, the price is always K baht.

So when you want to go from one island to another you always have two options. Get a boat to a neighboring island, where the price varies according to the route, or get a flight.

The islands are numbered from 1 to N. Your task is to determine the minimum expected price of a trip from island 1 to N.

Input

The first line has a single integer T, the number of test cases.

The first line of each test case has 3 integers, N, M, and K, that represents the number of islands, the number of boats, and the cost of getting a flight, respectively.

The next M lines contain 3 integers each, A, B, C, indicating that there exists a boat trip that costs C baht to go from island A to B or from B to A. There exists at most one boat servicing each pair of islands.

Limits

  • 1 ≤ T ≤ 20
  • 1 ≤ N, M ≤ 105
  • 1 ≤ C ≤ 103
  • 1 ≤ K ≤ 103
Output

For each instance, print the minimum expected value of a trip from island 1 to island N. The error should not exceed 10 - 4.

Example
Input
2
3 3 1
1 2 10
1 3 20
2 3 5
3 3 100
1 2 10
1 3 20
2 3 5
Output
3.0000000000
15.0000000000