{"trustable":false,"sections":[{"title":"","value":{"format":"MD","content":"\u003cscript type\u003d\"text/x-mathjax-config\"\u003e\nMathJax.Hub.Config({\n tex2jax: {inlineMath: [[\u0027$$$\u0027,\u0027$$$\u0027], [\u0027$\u0027,\u0027$\u0027]], displayMath: [[\u0027$$$$$$\u0027,\u0027$$$$$$\u0027], [\u0027$$\u0027,\u0027$$\u0027]]}\n});\n\u003c/script\u003e\n\u003cscript type\u003d\"text/javascript\" async\n src\u003d\"https://cdnjs.cloudflare.com/ajax/libs/mathjax/2.7.1/MathJax.js?config\u003dTeX-AMS-MML_HTMLorMML\"\u003e\n\u003c/script\u003e\n\nMichael Scofield has just broken out of the prison. He now wants to go to a certain city for his next unfinished job. As you are the only programmer in his gang, he asked for your help.\n\nAs you know that the fuel prices vary in the cities, you have to write a code to help Scofield that instructs him where to take the fuel and which path to choose. Assume that his car uses one unit of fuel in one unit of distance. Now he gives you the starting city **s** where he starts his journey with his car, the destination city **t** and the capacity of the fuel tank of his car **c**, the code should find the route that uses the cheapest fuel cost. You can assume that Scofield\u0027s car starts with an empty fuel tank.\n\n题意:n个点m条边的有向图,q次询问c,s,t,表示汽车油箱容量为c(c\u003c\u003d100),求从起点s到终点t的最小费用。汽车在每个点可以加任意的油,每个点的油价为a[i]。已知:一个单位的距离需要耗费1个单位的油量。"}},{"title":"Input","value":{"format":"MD","content":"Input starts with an integer **T (\u0026#8804; 5)**, denoting the number of test cases.\n\nEach case starts with a line containing two integers **n (2 \u0026#8804; n \u0026#8804; 100)** and **m (0 \u0026#8804; m \u0026#8804; 1000)** where **n** denotes the number of cities and **m** denotes the number of roads. The next line contains **n** space separated integers, each lies between **1** and **100**. The **i\u003csup\u003eth\u003c/sup\u003e** integer in this line denotes the fuel price (per unit) in the **i\u003csup\u003eth\u003c/sup\u003e** city. Each of the next **m** lines contains three integers **u v w (0 \u0026#8804; u, v \u0026lt; n, 1 \u0026#8804; w \u0026#8804; 100, u \u0026#8800; v)** denoting that there is a road between city **u** and **v** whose length is **w**.\n\nThe next line contains an integer **q (1 \u0026#8804; q \u0026#8804; 100)** denoting the number of queries by Scofield. Each of the next **q** lines contains the request. Each request contains three integers: **c s t (1 \u0026#8804; c \u0026#8804; 100, 0 \u0026#8804; s, t \u0026lt; n)** where **c** denotes the capacity of the tank, **s** denotes the starting city and **t** denotes the destination city."}},{"title":"Output","value":{"format":"MD","content":"For each case, print the case number first. Then for each query print the cheapest trip from **s** to **t** using the car with the given capacity **c** or `impossible` if there is no way of getting from **s** to **t** with the given car."}},{"title":"Sample Input","value":{"format":"MD","content":"\u003cpre\u003e1\n5 5\n10 10 20 12 13\n0 1 9\n0 2 8\n1 2 1\n1 3 11\n2 3 7\n2\n10 0 3\n20 1 4\n\u003c/pre\u003e"}},{"title":"Sample Output","value":{"format":"MD","content":"\u003cpre\u003eCase 1:\n170\nimpossible\n\u003c/pre\u003e"}}]}