Description

烽火台是一种传递信息的手段，通过在烽火台处燃起狼烟，使其他烽火台或要传递到的人看到，从而达到传递信息的目的。 已知有$N$个烽火台围绕一座城池，每个烽火台$k$燃起狼烟都需要一定的时间，记为该烽火台燃起狼烟所需的代价$W_k$，两座能够传递信息的烽火台$i、j$之间，因为距离等原因也需要一定的时间，记为传递信息的单位代价$V_{ij}$。 所有烽火台及若干传递信息的路径可以组成一棵树的结构。其中，树根为城池。每个烽火台为一个节点，若两座烽火台之间能够传递信息，则两烽火台之间存在一条边。对于每条边来说，传递信息的代价为 该边所连接的子树中所有点代价的和 $*$该边的单位代价。 根据输入数据，构建一棵树，使得所有边的总代价最小。

Format

Input

多组测试数据。

第一行两个整数$N、M（0 <= N,M <= 3000）$，为节点的数量及所有可能的边的数量。 第二行$N$个整数，第$k$个整数代表第$k$个节点的代价$W_k（1 <= Wk <= 2^{10}）$。 之后M行，每行$3$个整数$i、j、v$，代表第$i$个节点能够传递信息给第$j$个节点，传递信息的代价为$v（1 <= v <= 2^{10}）。$ 其中，城池为第$1$个节点。

Output

最小的总代价。 若有节点无法连接到根，则输出：$No$ $Answer$

Samples

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