问题 27004. -- Chris

27004: Chris

时间限制: 1 Sec  内存限制: 128 MB
献花: 40  解决: 16
[献花][花圈]

题目描述

圣诞节到了,FireDancer准备做一棵大圣诞树。左图为圣诞树的一个简单结构。

这棵树被表示成一组被编号的结点和一些边的集合。结点从1n编号。树的根永远是1。每个结点都有一个自身特有的数值,称为它的重。各个结点的重可能不同。对于一棵做完的树来说,每条边都有一个价值,若设这条边e连接结点i和结点j,且ij的父结点(根是最老的祖先),则该边的价值为(j的所有子孙及它自己的重之和)*e的单位价值ce)。

现在FireDancer想造一棵树,使得树上所有边的总价值最小,并且所有的点都在树上,因为FireDancer喜欢大树。

输入

第一行两个整数nm0<=n,m<=50000),表示结点总数和可供选择的边数。

下面一行有n个整数,依次表示每个结点的重。

下面m行,每行有3个正整数a,b,c,表示结点a和结点b之间有一个单位价值为c的边可供你造树时选择。

输入中的所有数都小于216

输出

若无解,输出“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

提示

来源

[献花][花圈]