/ 
Time Limit: 2 sec / Memory Limit: 1024 MB
配点 : 600 点
問題文
しおむすび君は次のような問題を解いています。
Paken 王国は N 個の街 1, 2, \ldots, N と M 本の道路 1, 2, \ldots, M からなります。 道路の情報を表す長さ M の数列 A,B,C が与えられていて、道路 i は街 A_i と街 B_i を双方向に結び、通るのに C_i のコストがかかります。
Paken 王国では、技術室奥プログラミングコンテスト#6の開催に合わせて N 日間に渡りイベントを開催します。 i 日目には街 i でイベントが開催されるので、街 i に行く必要があります。 i = 1, 2, \ldots, N について、 i 日目に街 1 から街 i を通り街 N まで移動するのにかかるコストの合計の最小値を求めて下さい。 ただし、頂点 1,N も含め同じ頂点や同じ道路を複数回通ってもいいものとします。
しおむすび君にかかればこの問題は簡単です。 しおむすび君は i = 1, 2, \ldots, N それぞれについて、 i 日目の答えが D_i であると分かりました。
しかししおむすび君は抜けているところがあるので、 A, B, C が何であったか忘れてしまいました。 しおむすび君のために A, B, C として考えられるものを 1 つ見つけてあげてください。
ただし、そのようなものが存在しないときは、それを報告してください。
制約
- 1 \leq N,M \leq 10^5
- 0 \leq D_i \leq 10^9 (1 \leq i \leq N)
- 入力は全て整数
入力
入力は以下の形式で標準入力から与えられる。
N M D_1 D_2 \ldots D_N
出力
条件を満たす A, B, C が存在しない場合、一行に No と出力せよ。存在する場合、以下の形式で出力せよ。
Yes A_1 B_1 C_1 A_2 B_2 C_2 \vdots A_M B_M C_M
ただし、これは以下の制約を満たす必要がある。
- 1 \leq A_i < B_i \leq N (1 \leq i \leq M)
- 0 \leq C_i \leq 10^9 (1 \leq i \leq M)
- (A_i, B_i) \neq (A_j, B_j) (1 \leq i < j \leq M)
- 任意の街から任意の街に 0 本以上の道路を使い移動することができる
- 元の問題を解いたとき、 i 日目の答えが D_i になる
- 各 i\ (1 \leq i \leq M) において、C_i は整数である（14:51 追記）
なお、条件を満たす A, B, C が複数存在する場合、そのどれを出力してもよい。
入力例 1
5 7 5 5 6 6 5
出力例 1
Yes 1 2 1 1 3 2 1 4 6 2 4 5 2 5 4 3 4 3 4 5 1
この出力例では、例えば 3 日目に移動にかかるコストが最小になる経路は、道路 2, 6, 7 を順に通るものになります。 道路を移動するのにかかるコストはそれぞれ 2, 3, 1 なので、合計で 6 のコストがかかります。
入力例 2
5 4 10 10 10 10 10
出力例 2
Yes 1 2 1 2 3 2 3 4 3 4 5 4
入力例 3
3 100 1 3 2
出力例 3
No
条件を満たす A, B, C は存在しません。
原案: shiomusubi496