{"trustable":false,"sections":[{"title":"","value":{"format":"HTML","content":"\u003cp\u003e \u003cspan\u003e \u003c/span\u003e\u003c/p\u003e \n\u003cp\u003e \u003cspan\u003eThe country - \u003cspan\u003eAjobdesh\u003c/span\u003e has a lot of problems in traffic system. As the \u003cspan\u003eGovt\u003c/span\u003e. is very clever (!), they made a plan to use only one way roads. Two cities \u003cb\u003es\u003c/b\u003e and \u003cb\u003et\u003c/b\u003e are the two most important cities in the country and mostly people travel from \u003cb\u003es\u003c/b\u003e to \u003cb\u003et\u003c/b\u003e. That\u0027s why the \u003cspan\u003eGovt\u003c/span\u003e. made a new plan to introduce some new one way roads in the traffic system such that the time to travel from \u003cb\u003es\u003c/b\u003e to \u003cb\u003et\u003c/b\u003e is reduced.\u003c/span\u003e\u003c/p\u003e \n\u003cp\u003e \u0026nbsp;\u003c/p\u003e \n\u003cp\u003e \u003cspan\u003eBut since their budget is short, they can\u0027t construct more than \u003cb\u003ed\u003c/b\u003e roads. So, they want to construct at most \u003cb\u003ed\u003c/b\u003e new roads such that it becomes possible to reach \u003cb\u003et\u003c/b\u003e from \u003cb\u003es\u003c/b\u003e 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 \u003cb\u003es\u003c/b\u003e to \u003cb\u003et\u003c/b\u003e, which may allow at most \u003cb\u003ed\u003c/b\u003e newly proposed roads.\u003c/span\u003e\u003c/p\u003e"}},{"title":"Input","value":{"format":"HTML","content":"\u003cp\u003e \u003cspan\u003eInput starts with an integer \u003cb\u003eT (\u003c/b\u003e\u003cb\u003e≤ 30)\u003c/b\u003e, denoting the number of test cases.\u003c/span\u003e\u003c/p\u003e \n\u003cp\u003e \u003cspan\u003eEach case starts with a line containing four integers \u003cb\u003en (2 ≤ n ≤ 10000), m (0 ≤ m ≤ 20000), k (0 ≤ k ≤ 10000), d (0 ≤ d ≤ 10)\u003c/b\u003e where \u003cb\u003en\u003c/b\u003e denotes the number of cities, \u003cb\u003em\u003c/b\u003e denotes the number of existing roads and \u003cb\u003ek\u003c/b\u003e denotes the number of proposed new roads. The cities are numbered from \u003cb\u003e0\u003c/b\u003e to \u003cb\u003en-1\u003c/b\u003e and city \u003cb\u003e0\u003c/b\u003e is denoted as \u003cb\u003es\u003c/b\u003e and city \u003cb\u003e(n-1)\u003c/b\u003e is denoted as \u003cb\u003et\u003c/b\u003e.\u003c/span\u003e\u003c/p\u003e \n\u003cp\u003e \u003cspan\u003eEach of the next \u003cb\u003em\u003c/b\u003e lines contains a description of a road, which contains three integers \u003cb\u003e\u003cspan\u003eu\u003csub\u003ei\u003c/sub\u003e\u003c/span\u003e v\u003csub\u003ei\u003c/sub\u003e \u003cspan\u003ew\u003csub\u003ei\u003c/sub\u003e\u003c/span\u003e (0 ≤ \u003cspan\u003eu\u003csub\u003ei\u003c/sub\u003e\u003c/span\u003e, v\u003csub\u003ei\u003c/sub\u003e \u0026lt; n, \u003cspan\u003eu\u003csub\u003ei\u003c/sub\u003e\u003c/span\u003e ≠ v\u003csub\u003ei\u003c/sub\u003e\u003c/b\u003e\u003cb\u003e\u003csub\u003e\u003cspan\u003e,\u003c/span\u003e\u003c/sub\u003e 1 ≤ \u003cspan\u003ew\u003csub\u003ei\u003c/sub\u003e\u003c/span\u003e ≤ 1000)\u003c/b\u003e meaning that there is a road from \u003cb\u003e\u003cspan\u003eu\u003csub\u003ei\u003c/sub\u003e\u003c/span\u003e\u003c/b\u003e to \u003cb\u003ev\u003csub\u003ei\u003c/sub\u003e\u003c/b\u003e and it takes \u003cb\u003e\u003cspan\u003ew\u003csub\u003ei\u003c/sub\u003e\u003c/span\u003e\u003c/b\u003e minutes to travel in the road. There is at most one road from one city to another city.\u003c/span\u003e\u003c/p\u003e \n\u003cp\u003e \u003cspan\u003eEach of the next \u003cb\u003ek\u003c/b\u003e lines contains a proposed new road with three integers \u003cb\u003e\u003cspan\u003eu\u003csub\u003ei\u003c/sub\u003e\u003c/span\u003e v\u003csub\u003ei\u003c/sub\u003e \u003cspan\u003ew\u003csub\u003ei\u003c/sub\u003e\u003c/span\u003e (0 ≤ \u003cspan\u003eu\u003csub\u003ei\u003c/sub\u003e\u003c/span\u003e, v\u003csub\u003ei\u003c/sub\u003e \u0026lt; n, \u003cspan\u003eu\u003csub\u003ei\u003c/sub\u003e\u003c/span\u003e ≠ v\u003csub\u003ei\u003c/sub\u003e 1 ≤ \u003cspan\u003ew\u003csub\u003ei\u003c/sub\u003e\u003c/span\u003e ≤ 1000)\u003c/b\u003e meaning that the road will be from \u003cb\u003e\u003cspan\u003eu\u003csub\u003ei\u003c/sub\u003e\u003c/span\u003e\u003c/b\u003e to \u003cb\u003ev\u003csub\u003ei\u003c/sub\u003e\u003c/b\u003e and it will take \u003cb\u003e\u003cspan\u003ew\u003csub\u003ei\u003c/sub\u003e\u003c/span\u003e\u003c/b\u003e minutes to travel in the road. There can be at most one proposed road from one city to another city.\u003c/span\u003e\u003c/p\u003e"}},{"title":"Output","value":{"format":"HTML","content":"\u003cp\u003e \u003cspan\u003eFor each case, print the case number and the shortest path cost from \u003cb\u003es\u003c/b\u003e to \u003cb\u003et\u003c/b\u003e or \u003cb\u003e\"Impossible\"\u003c/b\u003e if there is no path from \u003cb\u003es\u003c/b\u003e to \u003cb\u003et\u003c/b\u003e.\u003c/span\u003e\u003c/p\u003e"}},{"title":"Sample Input","value":{"format":"HTML","content":"\u003cp\u003e \u003cspan\u003e2\u003c/span\u003e\u003c/p\u003e \n\u003cp\u003e \u003cspan\u003e4 2 2 2\u003c/span\u003e\u003c/p\u003e \n\u003cp\u003e \u003cspan\u003e0 1 10\u003c/span\u003e\u003c/p\u003e \n\u003cp\u003e \u003cspan\u003e1 3 20\u003c/span\u003e\u003c/p\u003e \n\u003cp\u003e \u003cspan\u003e0 2 5\u003c/span\u003e\u003c/p\u003e \n\u003cp\u003e \u003cspan\u003e2 3 14\u003c/span\u003e\u003c/p\u003e \n\u003cp\u003e \u003cspan\u003e2 0 1 0\u003c/span\u003e\u003c/p\u003e \n\u003cp\u003e \u003cspan\u003e0 1 100\u003c/span\u003e\u003c/p\u003e"}},{"title":"Sample Output","value":{"format":"HTML","content":"\u003cp\u003e \u003cspan\u003eCase 1: 19\u003c/span\u003e\u003c/p\u003e \n\u003cp\u003e \u003cspan\u003eCase 2: Impossible\u003c/span\u003e\u003c/p\u003e"}},{"title":"Hint","value":{"format":"HTML","content":"\u003cbr\u003e"}}]}