{"trustable":true,"prependHtml":"\u003cscript\u003e window.katexOptions \u003d { disable: true }; \u003c/script\u003e\n\u003cscript type\u003d\"text/x-mathjax-config\"\u003e\n MathJax.Hub.Config({\n tex2jax: {\n inlineMath: [[\u0027$$$\u0027,\u0027$$$\u0027], [\u0027$\u0027,\u0027$\u0027]],\n displayMath: [[\u0027$$$$$$\u0027,\u0027$$$$$$\u0027], [\u0027$$\u0027,\u0027$$\u0027]]\n }\n });\n\u003c/script\u003e\n\u003cscript async src\u003d\"https://mathjax.codeforces.org/MathJax.js?config\u003dTeX-AMS-MML_HTMLorMML\" type\u003d\"text/javascript\"\u003e\u003c/script\u003e","sections":[{"title":"","value":{"format":"HTML","content":"\u003cdiv class\u003d\"panel_content\"\u003e\u003cimg style\u003d\"max-width:100%;\" src\u003d\"CDN_BASE_URL/9a9fccf2e2906da7658f3a46278389d8?v\u003d1714278364\"\u003e\u003cbr\u003e 自1945年,美国曼哈顿计划团队引爆第一颗核弹以来,全球核武器的数量激增。\u003cbr\u003e 如今,福州大学的疯狂少年AekdyCoin拥有一些核武器,并想要摧毁我们的世界。幸运的是,我们神秘的间谍网络已经得知了他的计划。现在,我们需要阻止他。\u003cbr\u003e 但这艰巨的任务显然并不容易。首先,我们知道核武器的操作系统由一些相连的电站组成,形成了一个庞大而复杂的电力网络。每个电站都有自己的功率值。要启动核武器,必须耗费电力网络一半以上的功率。因此,我们首先需要使超过一半的电力失效。我们的坦克已经准备好在基地(ID为0)执行行动,我们必须驾驶它们在道路上行驶。对于一个电站,只有我们的坦克停在那里时我们才能控制它们。1单位距离需要1单位燃油。而我们有足够的坦克可供使用。\u003cbr\u003e 现在我们的指挥官想要知道此次行动中的最小燃油成本。\u003c/div\u003e"}},{"title":"输入","value":{"format":"HTML","content":"输入的第一行包含一个整数T,表示文件中测试用例的数量。\u003cbr\u003e 对于每个测试用例,第一行是两个整数n(1≤n≤100),m(1≤m≤10000),表示站点的数量(ID为1,2,3...n)和站点之间的道路数量(双向)。\u003cbr\u003e 然后是m行,每行是三个整数st(0≤st≤n),ed(0≤ed≤n),dis(0≤dis≤100),表示起点,终点和之间的距离。\u003cbr\u003e 然后是n行,每行是一个整数pow(1≤pow≤100),按ID顺序指定电站的功率。"}},{"title":"输出","value":{"format":"HTML","content":"此次行动中的最小燃油成本。\u003cbr\u003e 如果不存在,则输出\"impossible\"(不带引号)。"}},{"title":"样例","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\r\n2 3\r\n0 2 9\r\n2 1 3\r\n1 0 2\r\n1\r\n3\r\n2 1\r\n2 1 3\r\n1\r\n3\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e5\r\nimpossible\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e"}}]}