The Problem

X国发生了内战。起义军得到了广大人民的支持。在一次战役中,反动军队结集了大量兵力,围攻起义军的主堡W城。为支援前线,后方各个供给基地城市纷纷准备将物资运往W城。各基地及W城之间有的有公路相连。这就是说,有的基地不能将物资一次运到W城,必须通过中途的转运。
根据每条公路的长短和运送物资的多少,运送中将会有不同程度的损耗。现假设每条公路都有一个损耗系数,表示经过这条公路的物资总量与消耗量的比值。
另外,为保证物资安全到达,每个基地都会等所有要通过该基地转运的物资到齐后,连同本基地的物资一起,运到下一站。也就是说,从任何一个基地出发,都只能将物资运往另一基地,但允许多个基地的物资运往同一基地。
请编程预定出每个基地的运输路线,使到达W城的总物资最大。如果从某基地出发经过几条路走的结果都一样最优,则选择编号较小的路走。

输入

本题只包括一组测试数据。第一行给出两个整数n(2<=n<=100)与m。其中n表示有n-1个基地(编号为1到n-1)与一个W城(编号为n);m表示有m条公路。接下来n-1行,每行1个正整数(正整数<=50000),表示编号为1到n-1的基地要运送的物资数量。接下来m行描述了m条公路的情况,每一行有3个数,如 1 2 0.1。表示1号城市与2号城市之间有一条公路连接,其损耗系数为0.1。注意:数据给出的公路网,保证每个基地都能将物资运到W城。

输出

共n行。
第一行是运到W城的最大物资数(结果保留两位小数)。
接下来n-1行分别有一个数,代表每个基地将物资运往的下一个基地或W城的编号。

样例输入

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

样例输

40.00
3
3
5
5