SP368 CSTREET - Cobbled streets

## 题目背景 在一个遥远的地方，有一个令人难以置信的贵族大城镇的市政编年史中记载了以下故事： 从前，新登基的国王冈瑟决定访问他王国中的所有城镇。这个贵族大城镇的居民认为冈瑟国王会想看看他们城镇中最著名的建筑。对于这些贵族市民来说，国王要经过的所有街道都必须用石头铺成。不幸的是，由于他们把大部分积蓄用来建造世界上最高的大教堂，这个贵族大城镇当时并没有太多的钱。 有传言说，他们节俭的真正原因并不是国库空虚，而是许多人相信冈瑟是通过欺骗他的父亲埃文国王而登上王位的，并且在他年轻时与魔鬼订立了契约。但无论如何，贵族大城镇的居民决定只铺设通往每个主要建筑所必需的街道。 你能帮助贵族大城镇的居民找出哪些街道应该铺设吗？ 你可能需要知道，所有的主要建筑要么位于街道的尽头，要么位于交叉路口。此外，你可以假设所有建筑都通过给定的街道连接在一起。

$t$ \[测试用例的数量（$1 \le t \le 100$）\] $p$ \[铺设一弗隆街道的价格（正整数）\] $n$ \[城镇中的主要建筑数量（$1 \le n \le 1000$）\] $m$ \[城镇中的街道数量（$1 \le m \le 300000$）\] $a \ b \ c$ \[从建筑 $a$ 到建筑 $b$ 的街道长度为 $c$ 弗隆（长度以弗隆为单位，建筑编号从 $1$ 到 $n$）\]

对于每个测试用例，输出在铺设街道的情况下，能够到达城镇中所有主要建筑的最低价格。你可以假设结果将小于 $2^{32}$。

\[测试用例的数量 $t$ 满足 $1 \le t \le 100$\]， \[铺设一弗隆街道的价格 $p$ 是正整数\]， \[城镇中的主要建筑数量 $n$ 满足 $1 \le n \le 1000$\]， \[城镇中的街道数量 $m$ 满足 $1 \le m \le 300000$\]。