8429: 圣诞树_1
内存限制：128 MB
时间限制：1.000 S
评测方式：文本比较
命题人：
提交：2
解决：1
题目描述
KFC为了迎接圣诞节的到来，员工们打算准备一个大大的圣诞树。圣诞树的结构示意图如下图所示：
这颗圣诞树可以用一些结点和边来表示。结点的编号为1至n。树根的结点总是编号为1的结点。在树中每个结点有自己的重量。这些重量可以看作是互不相同的。因此每条边也可看作是不一样的，即各边的的单价也就不一样了。一条边的价格是它的所有子结点的重量总和×该边的单价。
员工们想花费最少的钱来准备这棵圣诞树。所有结点都是要被用进的。现在他们想请你帮忙来解决这个问题。
这颗圣诞树可以用一些结点和边来表示。结点的编号为1至n。树根的结点总是编号为1的结点。在树中每个结点有自己的重量。这些重量可以看作是互不相同的。因此每条边也可看作是不一样的，即各边的的单价也就不一样了。一条边的价格是它的所有子结点的重量总和×该边的单价。
员工们想花费最少的钱来准备这棵圣诞树。所有结点都是要被用进的。现在他们想请你帮忙来解决这个问题。
输入
第一行包含两个整数v和e(1 < = v，e < = 50000)，分别表示节点和边的数目。紧接下面一行包含v个正整数，表示编号1到n的结点重量，再下面e行，每一行三个正整数xi，yi，vi，表示边(xi,yi)的单价为vi。(所有数据都不超过2^16)
输出
输出一个整数表示准备这个圣诞树的可能的最小价格。如果没有办法将所有结点用进，输出“No Answer”。
样例输入 复制
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样例输出 复制
1210提示
题目源：PKU 3013