問題文

銀河系には $N$ 個のステーション（1, 2, ..., $N$）があり、$M$ 個の一方向時空ワープゲートで結ばれています。
$i$ 番目のワープゲートはステーション $u_i$ から $v_i$ へ移動可能で、移動にかかる所要時間は $t_i$ です。
一部のゲートは時空の歪みにより時間が巻き戻る（$t_i < 0$）ことがありますが、時間を無限に遡れるような閉路（負の閉路）は存在しないことが保証されています。

各ステーション $i$ には「基本コスト」 $P_i$ が設定されています。
宇宙船がステーション $A$ を出発し、いくつかのゲートを経由してステーション $B$（$A \neq B$）へ荷物を届けるとき、その配送のトータルコストは以下のように定義されます。

$$\text{Cost}(A, B) = (\text{ステーション } A \text{ から } B \text{ への最小所要時間}) + P_A + P_B$$

到達可能なすべての異なるステーションのペア $(A, B)$ における $\text{Cost}(A, B)$ の最小値を求めてください。
また、その最小値を達成するペア $(A, B)$ が何組存在するかを求めてください。

なお、到達可能なステーションのペア $(A, B)$ が $1$つ以上存在することが保証されています。

制約

• $2 \le N \le 2500$
• $1 \le M \le 5000$
• $1 \le u_i, v_i \le N$
• $u_i \neq v_i$
• $i \neq j$ のとき、$(u_i, v_i) \neq (u_j, v_j)$
• $-10^6 \le t_i \le 10^6$
• $-10^9 \le P_i \le 10^9$
• グラフに負の閉路は存在しない。
• 入力される値はすべて整数。

入力

入力は以下の形式で標準入力から与えられます。

$N$ $M$
$P_1$ $P_2$ $\dots$ $P_N$
$u_1$ $v_1$ $t_1$
$u_2$ $v_2$ $t_2$
$\vdots$
$u_M$ $v_M$ $t_M$

出力

最小コストと、その最小コストを達成するペアの個数をスペース区切りで1行に出力してください。 到達可能なペアが存在しない場合は -1 を出力してください。

最後に改行してください。

サンプル

4 4
10 20 15 25
1 2 5
2 3 5
1 3 12
3 4 5

35 2

4 4
0 0 0 0
1 2 -5
2 3 -5
3 1 15
4 1 10

-10 1