{"trustable":true,"sections":[{"title":"","value":{"format":"MD","content":"我们都知道,我们即将迎来一场盛大而令人兴奋的婚礼派对。我们计划为婚礼买一份礼物。但就在我们准备购买礼物的时候,我们发现我们有一场“团队练习比赛”要参加。在参加比赛之前,我们希望礼物能准备好。\n\n由于时间太紧,我们将试图在去比赛的路上购买礼物,并尽量拜访尽可能多的商店。城市地图由一个具有 **N** 个节点和 **M** 条边的图表示。**N** 个节点代表 **N** 个路口,**M** 条边代表连接城市的 **M** 条单向道路。每条道路都有一个代表使用该道路所需时间的成本。比赛在第 **N-1** 个路口进行,我们将从第 **0** 个路口开始我们的旅程。并且恰好有 **S** 个商店位于不同的路口。\n\n给定商店的位置,你必须找到从第 **0** 个路口到第 **N-1** 个路口的路线,该路线将以最短的时间访问最多数量的商店(首先最大化商店的数量,然后最小化访问它们所需的时间)。我们可以多次访问一个路口。"}},{"title":"输入","value":{"format":"MD","content":"输入以一个整数 **T (\u0026#8804; 50)** 开始,表示测试用例的数量。\n\n每个用例以三个非负整数 **N (2 \u0026#8804; N \u0026#8804; 500)**, **M (1 \u0026#8804; M \u0026#8804; 10000)** 和 **S (0 \u0026#8804; S \u0026#8804; 15)** 开始。下一行包含 **S** 个整数,表示商店的位置。接下来的 **M** 行中,每行包含三个整数 **u**, **v, w** **(0 \u0026lt; u, v \u0026lt; N, u \u0026#8800; v, 1 \u0026#8804; w \u0026#8804; 100)**,表示从 **u** 到 **v** 的道路,成本为 **w**。"}},{"title":"输出","value":{"format":"MD","content":"对于每个输入用例,你必须打印出案例编号和两个整数,表示我们可以在路上访问的最大商店数量以及在访问最大商店数量后到达第 **N-1** 个路口所需的最短时间。如果我们无法参加比赛,则打印 `Impossible`。更多细节请参见示例。"}},{"title":"样例","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"}}]}