{"trustable":true,"sections":[{"title":"","value":{"format":"MD","content":"In Dhaka, there are too many vehicles. So, the result is well known, yes, traffic jam. So, mostly people have to spend quite a time in the roads to go from one place to another.\n\nNow, the students have finally found a solution to this problem. The idea is to make all the roads one way. That means a vehicle can go through the roads in one way only. And to make the number of vehicles low, each vehicle has to pay a toll to use a road. Now you want to go from a place **s** to another place **t**. And you have a total of **p** taka in your pocket. Now you want to find the path which contains the highest toll road, to go from **s** to **t**. Remember that you can\u0027t use more than **p** taka.\n\n![Toll Management](CDN_BASE_URL/6191c879029bbe57902bc9f7b5edb76d?v\u003d1715616518)\n\nFor the given picture, **s \u003d 1, t \u003d 5** and **p \u003d 10**. There are three paths from 1 to 5.\n\n1. Path 1: **1 - 2 - 5**, total toll \u003d **11 (\u0026gt; p)**.\n2. Path 2: **1 - 3 - 5**, total toll \u003d **9 (\u0026le; p)**, 6 is the maximum toll.\n3. Path 3: **1 - 4 - 5**, total toll \u003d **9 (\u0026le; p)**, 5 is the maximum toll.\n\nThe maximum toll for a road of all of the paths having total toll not greater than **p** is 6."}},{"title":"Input","value":{"format":"MD","content":"Input starts with an integer **T (\u0026le; 10)**, denoting the number of test cases.\n\nEach case starts with five integers **N (2 \u0026le; N \u0026le; 10000), M (1 \u0026le; M \u0026le; 50000), s (1 \u0026le; s \u0026le; N), t (1 \u0026le; t \u0026le; N)** and **p (1 \u0026le; p \u0026le; 10\u003csup\u003e6\u003c/sup\u003e)** where **N** means the number of junctions and **M** means the number of roads connecting the junctions. Then there will be **M** lines each containing three integers **u v c**. **u** and **v** are junctions and there is a road from **u** to **v (1 \u0026le; u, v \u0026le; N, u \u0026ne; v)** and **c (0 \u0026le; c \u0026le; 10\u003csup\u003e5\u003c/sup\u003e)** is the toll needed for that road. There can be multiple roads between two junctions."}},{"title":"Output","value":{"format":"MD","content":"For each case, print the case number and the desired result. If no such result is found, print `-1`."}},{"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 6 1 5 10\n1 2 7\n2 5 4\n1 3 6\n3 5 3\n1 4 5\n4 5 4\n2 1 1 2 10\n1 2 20\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003eCase 1: 6\nCase 2: -1\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":"Dataset is huge, use faster I/O methods."}}]}