{"trustable":false,"sections":[{"title":"","value":{"format":"MD","content":"Banguland\u0027s traffic system is plagued by several issues. The government came up with a strategy to solely use one-way highways since they are too intelligent to manage the problem (!). The two most significant cities in the nation are **s** and **t**, and most people go from **s** to **t**. Because of this, a new proposal has been made to add some additional one-way highways to the traffic system, reducing the distance between **s** and **t**.\n\nDue to a limited budget, they can only build **d** roads. In order to make it feasible to go from **s** to **t** in a shorter amount of time, they intend to build at most **d** additional highways.\nFinding the optimum route from **s** to **t**, which would allow at most **d** fresh proposed roads, will now need you to consider both the current roads and the new roads that are being suggested."}},{"title":"Input","value":{"format":"MD","content":"Input starts with an integer **T (\u0026le; 30)**, denoting the number of test cases.\n\nEach case starts with a line containing four integers **n (2 \u0026le; n \u0026le; 10000), m (0 \u0026le; m \u0026le; 20000), k (0 \u0026le; k \u0026le; 10000), d (0 \u0026le; d \u0026le; 10)** where **n** denotes the number of cities, **m** denotes the number of existing roads and **k** denotes the number of proposed new roads. The cities are numbered from **0** to **n-1** and city **0** is denoted as **s** and city **(n-1)** is denoted as **t**.\n\nEach of the next **m** lines contains a description of a road, which contains three integers **u\u003csub\u003ei\u003c/sub\u003e v\u003csub\u003ei\u003c/sub\u003e w\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, 1 \u0026le; w\u003csub\u003ei\u003c/sub\u003e \u0026le; 1000)** meaning that there is a road from **u\u003csub\u003ei\u003c/sub\u003e** to **v\u003csub\u003ei\u003c/sub\u003e** and it takes **w\u003csub\u003ei\u003c/sub\u003e** minutes to travel in the road. There is at most one road from one city to another city.\n\nEach of the next **k** lines contains a proposed new road with three integers **u\u003csub\u003ei\u003c/sub\u003e v\u003csub\u003ei\u003c/sub\u003e w\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 1 \u0026le; w\u003csub\u003ei\u003c/sub\u003e \u0026le; 1000)** meaning that the road will be from **u\u003csub\u003ei\u003c/sub\u003e** to **v\u003csub\u003ei\u003c/sub\u003e** and it will take **w\u003csub\u003ei\u003c/sub\u003e** minutes to travel in the road. There can be at most one proposed road from one city to another city."}},{"title":"Output","value":{"format":"MD","content":"For each case, print the case number and the shortest path cost from **s** to **t** or `Impossible` if there is no path from **s** to **t**."}},{"title":"Sample","value":{"format":"MD","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\n4 2 2 2\n0 1 10\n1 3 20\n0 2 5\n2 3 14\n2 0 1 0\n0 1 100\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003eCase 1: 19\nCase 2: Impossible\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."}}]}