{"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 class\u003d\"panel_content\"\u003e\n在努力了很多年以后,wyt 收到了飞行员驾驶证。为了庆祝一下,他为自己买了一架飞机并且准备环游全球。\n\u003cbr\u003e\n\u003cbr\u003e\n在地球上有 $n$ 个国家,编号为 $1 \\sim n$。有 $m$ 条航线连接,第 $i$ 条航线连接 $v_i$ 和 $u_i$ 两个国家,然后如果要使用这条航线需要花费 $w_i$ 升的燃油。\n\u003cbr\u003e\n\u003cbr\u003e\n保证他能从第一个国家通过各个航线飞到其它任一国家。\n\u003cbr\u003e\n\u003cbr\u003e\nwyt 现在在编号为 $1$ 的国家,请问他访问每个国家至少一次并且回到 $1$ 的最少燃油量。\n\u003c/div\u003e"}},{"title":"输入格式","value":{"format":"HTML","content":"\u003cbr\u003e\n第一行是一个整数 $T$,表示有 $T$ 组数据。\n\u003cbr\u003e\n\u003cbr\u003e\n在每组数据中,第一行有两个整数 $n, m$,$n$ 表示国家数量,$m$ 表示航线的数量\n\u003cbr\u003e\n\u003cbr\u003e\n接下来是 $m$ 行,每行输入三个整数 $u_i, v_i, w_i$,代表一条从 $u_i$ 到 $v_i$ 的燃油量为 $w_i$ 的航线。\n\u003cbr\u003e\n\u003cbr\u003e\n$1\\leq T\\leq 20$.\n\u003cbr\u003e\n\u003cbr\u003e\n$1\\leq n\\leq 16$.\n\u003cbr\u003e\n\u003cbr\u003e\n$1\\leq m\\leq 100000$.\n\u003cbr\u003e\n\u003cbr\u003e\n$1\\leq w_i\\leq 100$.\n\u003cbr\u003e\n\u003cbr\u003e\n$1\\leq u_i, v_i \\leq n$."}},{"title":"输出格式","value":{"format":"HTML","content":"输出 $T$ 行,第 $i$ 个数字代表第 $i$ 组数据所需要的最少燃油量。"}},{"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\u003e\u003cpre\u003e1\n3 2\n1 2 2\n1 3 3\u003c/pre\u003e\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e\u003cpre\u003e10\u003c/pre\u003e\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e\n"}}]}