AT_tkppc6_2_f Shortest Path Construction

[problemUrl]: https://atcoder.jp/contests/tkppc6-2/tasks/tkppc6_2_f しおむすび君は次のような問題を解いています。 > 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 $ つ見つけてあげてください。 ただし、そのようなものが存在しないときは、それを報告してください。

入力は以下の形式で標準入力から与えられる。 > $ 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\

### 制約 - $ 1\ \leq\ N,M\ \leq\ 10^5 $ - $ 0\ \leq\ D_i\ \leq\ 10^9 $ $ (1\ \leq\ i\ \leq\ N) $ - 入力は全て整数 ### Sample Explanation 1 この出力例では、例えば $ 3 $ 日目に移動にかかるコストが最小になる経路は、道路 $ 2,\ 6,\ 7 $ を順に通るものになります。 道路を移動するのにかかるコストはそれぞれ $ 2,\ 3,\ 1 $ なので、合計で $ 6 $ のコストがかかります。 ### Sample Explanation 3 条件を満たす $ A,\ B,\ C $ は存在しません。 原案: \[shiomusubi496\](https://atcoder.jp/users/shiomusubi496)