编程介的小学生 2016-12-30 02:44 采纳率: 20.5%
浏览 846
已采纳

Big Christmas Tree

Description

Christmas is coming to KCM city. Suby the loyal civilian in KCM city is preparing a big neat Christmas tree. The simple structure of the tree is shown in right picture.

The tree can be represented as a collection of numbered nodes and some edges. The nodes are numbered 1 through n. The root is always numbered 1. Every node in the tree has its weight. The weights can be different from each other. Also the shape of every available edge between two nodes is different, so the unit price of each edge is different. Because of a technical difficulty, price of an edge will be (sum of weights of all descendant nodes) × (unit price of the edge).

Suby wants to minimize the cost of whole tree among all possible choices. Also he wants to use all nodes because he wants a large tree. So he decided to ask you for helping solve this task by find the minimum cost.

Input

The input consists of T test cases. The number of test cases T is given in the first line of the input file. Each test case consists of several lines. Two numbers v, e (0 ≤ v, e ≤ 50000) are given in the first line of each test case. On the next line, v positive integers wi indicating the weights of v nodes are given in one line. On the following e lines, each line contain three positive integers a, b, c indicating the edge which is able to connect two nodes a and b, and unit price c.

All numbers in input are less than 216.

Output

For each test case, output an integer indicating the minimum possible cost for the tree in one line. If there is no way to build a Christmas tree, print “No Answer” in one line.

Sample Input

2
2 1
1 1
1 2 15
7 7
200 10 20 30 40 50 60
1 2 1
2 3 3
2 4 2
3 5 4
3 7 2
3 6 3
1 5 9
Sample Output

15
1210

  • 写回答

1条回答 默认 最新

  • threenewbee 2017-01-01 10:50
    关注
    本回答被题主选为最佳回答 , 对您是否有帮助呢?
    评论

报告相同问题?

悬赏问题

  • ¥15 寻一个支付宝扫码远程授权登录的软件助手app
  • ¥15 解riccati方程组
  • ¥15 display:none;样式在嵌套结构中的已设置了display样式的元素上不起作用?
  • ¥30 用arduino开发esp32控制ps2手柄一直报错
  • ¥15 使用rabbitMQ 消息队列作为url源进行多线程爬取时,总有几个url没有处理的问题。
  • ¥15 求chat4.0解答一道线性规划题,用lingo编程运行,第一问要求写出数学模型和lingo语言编程模型,第二问第三问解答就行,我的ddl要到了谁来求了
  • ¥15 Ubuntu在安装序列比对软件STAR时出现报错如何解决
  • ¥50 树莓派安卓APK系统签名
  • ¥65 汇编语言除法溢出问题
  • ¥15 Visual Studio问题