{"trustable":true,"sections":[{"title":"","value":{"format":"MD","content":"Alice and Bob are trying to communicate through the internet. Just assume that there are **N** routers in the internet and they are numbered from **0** to **N-1**. Alice is directly connected to router **0** and Bob is directly connected to router **N-1**. Alice initiates the connection and she wants to send **S** KB of data to Bob. Data can go to the **(N-1)\u003csup\u003eth\u003c/sup\u003e** router from the **0\u003csup\u003eth\u003c/sup\u003e** router either directly or via some intermediate routers. There are some bidirectional links between some routers.\n\nThe links between the routers are not necessarily 100% perfect. So, for each link, a probability **p\u003csub\u003ei\u003c/sub\u003e** is given. If **u** and **v** are two routers and if their underlying link has probability **p\u003csub\u003ei\u003c/sub\u003e**, it means that if data is sent from **u** to **v**, the probability of successfully getting the data in **v** is **p\u003csub\u003ei\u003c/sub\u003e** and vice versa. If multiple links are used, the probability of getting the data in destination is the multiplication of the probabilities of the links that have been used.\n\nAssume that it takes exactly **K** seconds for a packet to reach Bob\u0027s router from Alice\u0027s router (independent of the number of links) if it\u0027s successful. And when the data is successfully received in Bob\u0027s router, it immediately sends an acknowledgement to Alice\u0027s router and the acknowledgement always reaches her router exactly in **K** seconds (it never disappears).\n\nAlice\u0027s router used the following algorithm for the data communication:\n\n1. At time 0, the first KB of data is chosen to be sent.\n2. It establishes a path (it takes no time) to the destination router and sends the data in this route.\n3. It waits for exactly **2K** seconds.\n 1. If it gets the acknowledgement of the current data in this interval:\n 1. If **S** KB of data are sent, then step 4 is followed.\n 2. Otherwise, it takes 1 KB of the next data, and then step 2 is followed.\n 2. Otherwise it resends the current 1 KB of data and then step 2 is followed. \n4. All the data are sent, so it reports Alice.\n\nAssume that the probabilities of the links are static and independent. That means it doesn\u0027t depend on the result of the previously sent data. Now your task is to choose some routes through the routers such that data can be sent in these routes and the expected time to send all the data to the destination routes is minimized. You only have to report the minimum expected time."}},{"title":"Input","value":{"format":"MD","content":"Input starts with an integer **T (\u0026le; 100)**, denoting the number of test cases.\n\nEach case starts with a line containing four integers **N (2 \u0026le; N \u0026le; 100)**, **M (1 \u0026le; M)**, **S (1 \u0026le; S \u0026le; 10\u003csup\u003e9\u003c/sup\u003e)** and **K (1 \u0026le; K \u0026le; 20)**, where **M** denotes the number of bidirectional links. Each of the next **M** lines contains three integers **u\u003csub\u003ei\u003c/sub\u003e v\u003csub\u003ei\u003c/sub\u003e p\u003csub\u003ei\u003c/sub\u003e**, meaning that there is a link between router **u\u003csub\u003ei\u003c/sub\u003e** and **v\u003csub\u003ei\u003c/sub\u003e** the the probability of a successful message transfer in this link is **p\u003csub\u003ei\u003c/sub\u003e%** **(0 \u0026le; u\u003csub\u003ei\u003c/sub\u003e, v\u003csub\u003ei\u003c/sub\u003e \u0026lt; N, u\u003csub\u003ei\u003c/sub\u003e \u0026ne; v\u003csub\u003ei\u003c/sub\u003e, 0 \u0026lt; p\u003csub\u003ei\u003c/sub\u003e \u0026le; 100)**. There will be at most one link between any two routers."}},{"title":"Output","value":{"format":"MD","content":"For each case, print the case number and the minimum possible expected time to send all the data. Errors less than **10\u003csup\u003e-3\u003c/sup\u003e** will be ignored. You can assume that at least one valid route between them always exists. And the result will be less than **10\u003csup\u003e13\u003c/sup\u003e**."}},{"title":"Sample","value":{"format":"HTML","content":"\u003ctable class\u003d\u0027vjudge_sample\u0027\u003e\n\u003cthead\u003e\n \u003ctr\u003e\n \u003cth\u003eInput\u003c/th\u003e\n \u003cth\u003eOutput\u003c/th\u003e\n \u003c/tr\u003e\n\u003c/thead\u003e\n\u003ctbody\u003e\n \u003ctr\u003e\n \u003ctd\u003e\u003cpre\u003e2\n5 5 1 10\n0 1 70\n0 2 40\n2 3 100\n1 3 50\n4 3 80\n2 1 30 2\n0 1 80\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003eCase 1: 62.5000000000\nCase 2: 150.0000000000\n\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e\n"}},{"title":"Note","value":{"format":"MD","content":"For sample 1, we get the following picture. We send the data through 0 - 2 - 3 - 4.\n\n![Packet](CDN_BASE_URL/597770b62cc646b471824652392655e4?v\u003d1714587357)"}}]}