{"trustable":false,"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\u003e \n \u003cimg src\u003d\"http://7xjob4.com1.z0.glb.clouddn.com/9a9fccf2e2906da7658f3a46278389d8\"\u003e\n \u003cbr\u003e Since 1945, when the first nuclear bomb was exploded by the Manhattan Project team in the US, the number of nuclear weapons have soared across the globe.\n\u003c/div\u003e \n\u003cdiv\u003e\n 自从1945年曼哈顿计划小组在美国引爆了第一颗原子弹,世界核武器的数量已经飙升了。\n\u003c/div\u003e \n\u003cdiv\u003e \n \u003cbr\u003e Nowadays,the crazy boy in \n \u003cspan\u003e\u003cspan\u003e\u003cspan\u003e\u003cspan\u003e\u003cspan\u003eFZU\u003c/span\u003e\u003c/span\u003e\u003c/span\u003e\u003c/span\u003e\u003c/span\u003e named \n \u003cspan\u003e\u003cspan\u003e\u003cspan\u003e\u003cspan\u003e\u003cspan\u003eAekdyCoin\u003c/span\u003e\u003c/span\u003e\u003c/span\u003e\u003c/span\u003e\u003c/span\u003e possesses some nuclear weapons and \n \u003cspan\u003e\u003cspan\u003e\u003cspan\u003e\u003cspan\u003e\u003cspan\u003ewanna\u003c/span\u003e\u003c/span\u003e\u003c/span\u003e\u003c/span\u003e\u003c/span\u003e destroy our world. Fortunately, our mysterious spy-net has gotten his plan. Now, we need to stop it.\n\u003c/div\u003e \n\u003cdiv\u003e\n 如今,FZU的一个名为AekdyCoin的疯狂的男孩拥有一些核武器,并想摧毁我们的世界。幸运的是,我们的神秘间谍网络已经得到了他的计划。现在,我们需要阻止它。\n\u003c/div\u003e \n\u003cdiv\u003e \n \u003cbr\u003e But the arduous task is obviously not easy. First of all, we know that the operating system of the nuclear weapon consists of some connected electric stations, which forms a huge and complex electric network. Every electric station has its power value. To start the nuclear weapon, it must cost half of the electric network\u0027s power. So first of all, we need to make more than half of the power \n \u003cspan\u003e\u003cspan\u003e\u003cspan\u003e\u003cspan\u003e\u003cspan\u003ediasbled\u003c/span\u003e\u003c/span\u003e\u003c/span\u003e\u003c/span\u003e\u003c/span\u003e. Our tanks are ready for our action in the base(ID is 0), and we must drive them on the road. As for a electric station, we control them if and only if our tanks stop there. 1 unit distance costs 1 unit oil. And we have enough tanks to use.\n\u003c/div\u003e \n\u003cdiv\u003e\n 但是,这个艰巨的任务显然是不容易的。首先,我们知道,核武器的操作系统包括一些连接的电站,这形成了一个庞大而复杂的电网。每个电站都有其电力值。要启动核武器,就必须花费电网的电力的一半。所以首先,我们需要让超过一半的电力失效。我们的坦克们已经在基地(ID为0)为本次行动准备好,我们必须让他们开上道路。对于一个电站,我们控制他们当且仅当我们的坦克停在那里。 1单位距离花费1个单位的石油。并且我们有足够的坦克使用。\n\u003c/div\u003e \n\u003cdiv\u003e \n \u003cbr\u003e Now our commander wants to know the minimal oil cost in this action.\n\u003c/div\u003e \n\u003cdiv\u003e\n 现在,我们的指挥官想知道这个行动的最小油耗。\n\u003c/div\u003e"}},{"title":"Input","value":{"format":"HTML","content":"\u003cp\u003e The first line of the input contains a single integer T, specifying the number of \u003cspan\u003e\u003cspan\u003e\u003cspan\u003e\u003cspan\u003e\u003cspan\u003etestcase\u003c/span\u003e\u003c/span\u003e\u003c/span\u003e\u003c/span\u003e\u003c/span\u003e in the file.\u003cbr\u003e For each case, first line is the integer n(1\u0026lt;\u003d n\u0026lt;\u003d 100), m(1\u0026lt;\u003d m\u0026lt;\u003d 10000), specifying the number of the stations(the IDs are 1,2,3...n), and the number of the roads between the station(bi-direction).\u003cbr\u003e Then m lines follow, each line is \u003cspan\u003e\u003cspan\u003e\u003cspan\u003e\u003cspan\u003e\u003cspan\u003einterger\u003c/span\u003e\u003c/span\u003e\u003c/span\u003e\u003c/span\u003e\u003c/span\u003e \u003cspan\u003e\u003cspan\u003e\u003cspan\u003e\u003cspan\u003e\u003cspan\u003est\u003c/span\u003e\u003c/span\u003e\u003c/span\u003e\u003c/span\u003e\u003c/span\u003e(0\u0026lt;\u003d st\u0026lt;\u003d n), \u003cspan\u003e\u003cspan\u003e\u003cspan\u003e\u003cspan\u003e\u003cspan\u003eed\u003c/span\u003e\u003c/span\u003e\u003c/span\u003e\u003c/span\u003e\u003c/span\u003e(0\u0026lt;\u003d ed\u0026lt;\u003d n), \u003cspan\u003e\u003cspan\u003e\u003cspan\u003e\u003cspan\u003e\u003cspan\u003edis\u003c/span\u003e\u003c/span\u003e\u003c/span\u003e\u003c/span\u003e\u003c/span\u003e(0\u0026lt;\u003d dis\u0026lt;\u003d 100), specifying the start point, end point, and the distance between.\u003cbr\u003e Then n lines follow, each line is a \u003cspan\u003e\u003cspan\u003e\u003cspan\u003e\u003cspan\u003e\u003cspan\u003einterger\u003c/span\u003e\u003c/span\u003e\u003c/span\u003e\u003c/span\u003e\u003c/span\u003e pow(1\u0026lt;\u003d pow\u0026lt;\u003d 100), specifying the electric station\u0027s power by ID order.\u003c/p\u003e"}},{"title":"Output","value":{"format":"HTML","content":"\u003cp\u003e The minimal oil cost in this action.\u003cbr\u003e If not exist print \"impossible\"(without quotes).\u003c/p\u003e"}},{"title":"Sample Input","value":{"format":"HTML","content":"\u003cpre\u003e\r\n2\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"}},{"title":"Sample Output","value":{"format":"HTML","content":"\u003cpre\u003e\r\n5\r\nimpossible\u003c/pre\u003e"}}]}