Brotherhood在KWAI建立了分部,但由于燕大人杰地灵,不是什么人都能够任意进出的,于是现在一个棘手的问题摆在了Ezio面前:情报的传递。
已知燕大内的Brotherhood一共有 n 个团体,有些团体之间有一些关系,你可以把它们看作一条边,每条边连接了两个 **不同** 的团体,现在一共有 m 条边。
现在前辈 Jumbo 要求 Ezio 将一个情报传递给燕大内的所有团体。已知 Ezio 亲自去向团体i告知情报的代价为 val[i] 。Ezio 当然不想一个一个去找啦,他还有很多任务要完成,于是他发现他可以利用团体之间的关系,让某一个已经被传达过情报的团体去告知另一与之有关系团体。
但是团体内部的人懒癌发作,自然不想白白地去帮 Ezio跑 腿。具体来说,针对关系 (u,v) ,如果 Ezio 想要利用它,应该付出的代价为cost(u,v)。
简而言之:
一个团体得到情报有两种方式:
1.由 Ezio 亲自告知,即代价为 val[i]。
2.由一个与之有关系且已经得到情报的团体以 cost(u,v) 为代价得到情报。
输入的第一行表示测试数据组数,满足
数据范围:每组测试用例满足 ,
数据范围:每组测试用例满足 ,