Problem B: 战争准备

Problem B: 战争准备

Time Limit: 1 Sec  Memory Limit: 128 MB
Submit: 111  Solved: 35
[Submit] [Status] [Web Board] [Creator:]

Description

        中国有句古话叫做“兵马未动粮草先行”,一天H国的国王szhc因不满S国国王hhskr嘲笑他……,他就决定发动战争。首先他让所有的城市向首都运粮草。根据道路的长度和重量的货物,运输期间会有一些成本。每路的成本率等于所花的成本的重量除以在该路上运输货物的重量的商。它是保证成本率小于1。另一方面,每个城市都必须等到所有货物到达,然后运输到达货物连同自己的货物到下一个城市。一个城市只会运输一次货物。

        你的任务是找到货物的最大重量可抵达首都。


Input

        有多组样例

        对于每种样例下,第一行有两个整数N (2 N 100)M1M10000,其中N是城市的数量包括首都(首都编号是N,其他城市编号1N - 1),M是道路的数量。

然后遵循n - 1行。第i(1 i N - 1)行包含一个正整数(< = 5000)代表货物的重量的第i个城市将运输到首都。

        下面的M线表示M道路。有三个数字ABC的每一行代表城市AB之间有一条路,这条路的成本率是C。      

文本结束符结束

Output

对于每一个样例输出一行表示可抵达首都货物的最大重量(保留两位小数)

Sample Input Copy

5 6
10
10
10
10
1 3 0
1 4 0
2 3 0
2 4 0
3 5 0
4 5 0

Sample Output Copy

40.00