Random Walks in Thailand
By Stefano Tommasini, Universidade de São Paulo 
Brazil
By Stefano Tommasini, Universidade de São Paulo Brazil
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 neighbouring 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 of the input has an integer T corresponding to the number of instances.
The first line of each instance has 3 integers, N, M (1 ≤ N, M ≤ 100.000), and K (1 ≤ K ≤ 1000), 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 (1 ≤ C ≤ 1000), 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.
For each instance, print a real number rounded to 3 decimal digits with the minimum expected value. The number should be printed with exactly 3 decimal digits.
| Input Sample | Output Sample |
|
2 3 3 1 0 1 10 0 2 20 1 2 5 3 3 100 0 1 10 0 2 20 1 2 5 |
3.000 15.000 |