{"trustable":true,"sections":[{"title":"","value":{"format":"MD","content":"You, a programmer of an important software house, have been fired because you didn\u0027t solve an important problem that was assigned to you. You are very furious and want to take revenge on your boss, breaking the communication between his computer and the central server.\n\nThe computer of your boss and the central server are in the same network, which is composed of many machines (computers) and wires linking pairs of those machines. There is at most one wire between any pair of machines and there can be pairs of machines without a wire between them.\n\nTo accomplish your objective, you can destroy machines and wires, but you can\u0027t destroy neither the computer of your boss, nor the central server, because those machines are monitored by security cameras. You have estimated the cost of blowing up each machine and the cost of cutting each wire in the network.\n\nYou want to determine the minimum cost of interrupting the communication between your boss\u0027 computer and the central server. Two computers **A** and **B** can communicate if there is a sequence of undestroyed machines **x\u003csub\u003e1\u003c/sub\u003e, x\u003csub\u003e2\u003c/sub\u003e, ..., x\u003csub\u003en\u003c/sub\u003e** such that **x\u003csub\u003e1\u003c/sub\u003e \u003d A**, **x\u003csub\u003en\u003c/sub\u003e \u003d B** and **x\u003csub\u003ei\u003c/sub\u003e** is linked with **x\u003csub\u003ei\u003c/sub\u003e+1** with an uncut wire (for each **1 \u0026le; i \u0026lt; n**)."}},{"title":"Input","value":{"format":"MD","content":"Input starts with an integer **T (\u0026le; 50)**, denoting the number of test cases.\n\nEach case starts with two integers **M (2 \u0026le; M \u0026le; 50)** and **W (0 \u0026le; W \u0026le; 1200)** where **M** denotes the number of machines and **W** denotes the number of wires. The ids of the boss\u0027 machine and the server are **1** and **M** respectively. The next line contains **M - 2** integers denoting the cost for destroying the machines from **2** to **M - 1** respectively. Each of the next **W** lines contains three integers **i j c**, meaning that the wire between machine **i** and **j** can be destroyed with the cost of **c**. All the destroying costs are between **0** and **10\u003csup\u003e5\u003c/sup\u003e**."}},{"title":"Output","value":{"format":"MD","content":"For each case, print the case number and the minimum cost of interrupting the communication between the computer of your boss and the central server."}},{"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 4\n2 5\n1 2 3\n1 3 3\n2 4 1\n3 4 3\n4 4\n2 2\n1 2 3\n1 3 3\n2 4 1\n3 4 3\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003eCase 1: 4\nCase 2: 3\n\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e\n"}}]}