{"trustable":false,"sections":[{"title":"","value":{"format":"MD","content":"We all know that we have a big and exciting wedding party ahead. We made a plan to buy a gift for the wedding. But just when we were about to busy the gift , we found out that we have a \u0027Team Practice Contest\u0027 ahead. Before going to the contest, we want the gift to be ready.\n\nAs time is too short, we will try to buy the gift on the way to the contest and will try to visit as many shops as possible. The city map is represented by a graph with **N** nodes and **M** edges. **N** nodes represent the **N** junctions and **M** edges represent the **M** unidirectional roads connecting the cities. Every road has a cost which represents the required time to use the road. The contest is running at junction **N-1** and we will start our journey at junction **0**. And there are exactly **S** shops located at different junctions.\n\nGiven the location of the shops you have to find the route from junction **0** to junction **N-1** which will visit maximum number of shops with minimum time (first maximize the number of shops then minimize the time to visit them). We can visit a junction more than once.\n\n题目大意:一个人要从0点走到n-1点,路中有些点有商店可以买礼物,所以这个人想买多点礼物,但是又要尽快的走到n-1点。礼物的多少优先,其次是路程长度。"}},{"title":"Input","value":{"format":"MD","content":"Input starts with an integer **T (\u0026#8804; 50)**, denoting the number of test cases.\n\nEach case begins with three non negative integers\u0026nbsp;**N (2 \u0026#8804; N \u0026#8804; 500)**, **M (1 \u0026#8804; M \u0026#8804; 10000)** **S (0 \u0026#8804; S \u0026#8804; 15)**. Next line contains **S** integers denoting the shop locations. Each of the next **M** lines contains three integers **u**, **v, w** **(0 \u0026lt; u, v \u0026lt; N, u \u0026#8800; v, 1 \u0026#8804; w \u0026#8804; 100)** denoting a road from **u** to **v** with cost **w**."}},{"title":"Output","value":{"format":"MD","content":"For each case of input you have to print the case number and two integers representing maximum number of shops we can visit in the way and the minimum time required to reach junction **N-1 **after visiting maximum number of shops. If we cannot attend the contest, print `Impossible`. See samples for more details."}},{"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 4 4\n0 1 2 3\n0 1 10\n1 3 30\n0 2 30\n2 3 5\n4 4 4\n0 1 2 3\n0 1 10\n3 1 30\n0 2 30\n3 2 5\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003eCase 1: 3 35\nCase 2: Impossible\n\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e\n"}}]}