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.
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*
For each instance, print the minimum expected value of a trip from island 1 to island N. The error should not exceed 10 - 4.
## 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.
[samples]
**Definitions**
Let $ T \in \mathbb{Z} $ be the number of test cases.
For each test case:
- Let $ N \in \mathbb{Z} $ be the number of islands, numbered $ 1 $ to $ N $.
- Let $ M \in \mathbb{Z} $ be the number of boat routes.
- Let $ K \in \mathbb{R}^+ $ be the fixed cost of a flight.
- Let $ G = (V, E) $ be an undirected graph where $ V = \{1, 2, \dots, N\} $ and each edge $ (A, B) \in E $ has weight $ C $, representing a bidirectional boat route from island $ A $ to $ B $ with cost $ C $.
**Constraints**
1. $ 1 \le T \le \text{some bound} $ (not specified, but assumed feasible)
2. $ 1 \le N \le \text{some bound} $, $ 0 \le M \le \binom{N}{2} $, $ K > 0 $
3. For each boat route: $ 1 \le A, B \le N $, $ A \ne B $, $ C > 0 $
4. At most one boat route between any pair of islands.
**Objective**
Define $ E[i] $ as the minimum expected cost to reach island $ N $ starting from island $ i $.
We seek $ E[1] $.
For each island $ i \in \{1, \dots, N-1\} $:
$$
E[i] = \min\left( \min_{(i,j) \in E} \{ C_{ij} + E[j] \},\; K + \frac{1}{N} \sum_{j=1}^{N} E[j] \right)
$$
With boundary condition:
$$
E[N] = 0
$$
The system of equations is solved for $ E[1], E[2], \dots, E[N-1] $, with $ E[N] = 0 $, using the above recurrence.