#P3013. Big Christmas Tree

    ID: 2014 传统题 1000ms 256MiB 尝试: 8 已通过: 1 难度: 10 上传者: 标签>图结构最短路POJ Monthly--2006.09.29KimChan Min (kcm1700@POJ)

Big Christmas Tree

题目描述

圣诞节即将来到KCM市。KCM市的忠实市民Suby正在准备一棵漂亮的大圣诞树。这棵树的基本结构如右图所示。

这棵树可以表示为由编号节点和若干边组成的集合。节点编号为11nn,根节点始终为11。树中每个节点都有其权重,各节点的权重可能不同。此外,每两个节点之间可用的边的形状也不同,因此每条边的单位价格也不同。由于技术限制,每条边的价格将等于(该边所有后代节点的权重之和)×(该边的单位价格)。

Suby希望在所有可能的选择中使整棵树的总成本最小。同时他希望使用所有节点,因为他想要一棵大树。因此他决定请你帮忙解决这个问题,找出最小成本。

输入格式

输入包含TT个测试用例。第一行输入测试用例数量TT。每个测试用例包含若干行:

  • 第一行给出两个数字vvee0v,e500000 \leq v, e \leq 50000),分别表示节点数量和可用边数量。
  • 第二行给出vv个正整数wiw_i,表示vv个节点的权重。
  • 接下来的ee行,每行包含三个正整数aabbcc,表示可以连接节点aabb的边,其单位价格为cc

输入中的所有数字均小于2162^{16}

输出格式

对于每个测试用例,输出一个整数表示该树的最小可能成本。如果无法构建圣诞树,则输出一行"No Answer"。

输入样例 1

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

输出样例 1

15
1210

题目来源

POJ Monthly--2006.09.29, Kim, Chan Min (kcm1700@POJ)