{"trustable":true,"sections":[{"title":"","value":{"format":"MD","content":"The country - Ajobdesh has a lot of problems in traffic system. As the Govt. is very clever (!), they made a plan to use only one way roads. Two cities **s** and **t** are the two most important cities in the country and mostly people travel from **s** to **t**. That\u0027s why the Govt. made a new plan to introduce some new one way roads in the traffic system such that the time to travel from **s** to **t** is reduced.\n\nBut since their budget is short, they can\u0027t construct more than **d** roads. So, they want to construct at most **d** new roads such that it becomes possible to reach **t** from **s** in shorter time. Unluckily you are one living in the country and you are assigned this task. That means you will be given the existing roads and the proposed new roads, you have to find the best path from **s** to **t**, which may allow at most **d** newly proposed roads."}},{"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":"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\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."}}]}