{"problem":{"name":"D. Random walks in Thailand","description":{"content":"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 boat","description_type":"Markdown"},"platform":"Codeforces","limit":{"time_limit":3000,"memory_limit":65536},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"CF10104D"},"statements":[{"statement_type":"Markdown","content":"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...\n\nFerry 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).\n\nThe 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.\n\nSo 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.\n\nThe islands are numbered from 1 to N. Your task is to determine the minimum expected price of a trip from island 1 to N.\n\nThe first line has a single integer T, the number of test cases.\n\nThe 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.\n\nThe 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.\n\n*Limits* \n\nFor each instance, print the minimum expected value of a trip from island 1 to island N. The error should not exceed 10 - 4.\n\n## Input\n\nThe 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 \n\n## Output\n\nFor each instance, print the minimum expected value of a trip from island 1 to island N. The error should not exceed 10 - 4.\n\n[samples]","is_translate":false,"language":"English"},{"statement_type":"Markdown","content":"**Definitions**  \nLet $ T \\in \\mathbb{Z} $ be the number of test cases.  \nFor each test case:  \n- Let $ N \\in \\mathbb{Z} $ be the number of islands, numbered $ 1 $ to $ N $.  \n- Let $ M \\in \\mathbb{Z} $ be the number of boat routes.  \n- Let $ K \\in \\mathbb{R}^+ $ be the fixed cost of a flight.  \n- 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 $.  \n\n**Constraints**  \n1. $ 1 \\le T \\le \\text{some bound} $ (not specified, but assumed feasible)  \n2. $ 1 \\le N \\le \\text{some bound} $, $ 0 \\le M \\le \\binom{N}{2} $, $ K > 0 $  \n3. For each boat route: $ 1 \\le A, B \\le N $, $ A \\ne B $, $ C > 0 $  \n4. At most one boat route between any pair of islands.  \n\n**Objective**  \nDefine $ E[i] $ as the minimum expected cost to reach island $ N $ starting from island $ i $.  \nWe seek $ E[1] $.  \n\nFor each island $ i \\in \\{1, \\dots, N-1\\} $:  \n$$\nE[i] = \\min\\left( \\min_{(i,j) \\in E} \\{ C_{ij} + E[j] \\},\\; K + \\frac{1}{N} \\sum_{j=1}^{N} E[j] \\right)\n$$  \nWith boundary condition:  \n$$\nE[N] = 0\n$$  \n\nThe system of equations is solved for $ E[1], E[2], \\dots, E[N-1] $, with $ E[N] = 0 $, using the above recurrence.","is_translate":false,"language":"Formal"}],"meta":{"iden":"CF10104D","tags":[],"sample_group":[],"created_at":"2026-03-03 11:00:39"}}