[省常中2011S4]聖誕節

成绩 0 开启时间 2013年02月21日 星期四 18:02
折扣 0.8 折扣时间 2013年02月28日 星期四 18:02
允许迟交 关闭时间 2013年02月28日 星期四 18:02
输入文件 chris.in 输出文件 chris.out

【题目描述】


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

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

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


【输入格式】


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

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

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

输入中的所有数都小于2^16。


【输出格式】


若无解,输出“No Answer”,否则一个整数表示造树的最小价值。


【样例输入】


[样例输入1]

Chris.in

2 1

1 1

1 2 15

[样例输入2]

Chris.in

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

[样例输出2]

1210

【来源】

江苏省常州市高级中学 曹文培训图论练习题