王国最近被敌对国家攻击了！众所周知，战争时期最需要破坏的就是通讯和粮草。
现在所有道路都已经被破坏了，王国的 n 个城市（编号为 1 ~ n）都处于孤立无援的状态
为了修复所有城市的通讯，使得国王下达的命令可以传递到所有城市
现在国王希望在某些城市建立 `军事基地`，在第 i 个城市建立 `军事基地` 所需要花费是 ai，`军事基地` 可以通过卫星直接接收到国王下达的命令
因为建立军事基地的花费比较大，也可以通过修复道路来使得两个城市可以传递信息
现在已知修复两个城市 i,j 之间道路需要的花费为 v{i,j}，并且这条道路是双向道路
现在因为正处于战争时期，所以资金非常紧张，王国希望以最小的花费使得他的命令可以传递到所有城市
注意：国王不处于任何城市之中，所以所有城市中至少要建立一个 `军事基地` 来接收信息