以下では頂点 \(u,v\) を結ぶ重み \(w\) の辺を \((u,v,w)\) と表します。

\(G\) の最小全域木を \(1\) つとり、これを \(T'\) とします。 最小全域木はクラスカル法によって得ることができ、とくに \(T'\) に含まれる辺 \((u_i,v_i,w_i)\) について、「頂点 \(u_i,v_i\) を結ぶ \(G\) 上のウォークは必ず重みが \(w_i\) 以上の辺を含む」が成り立ちます（★）。

これを踏まえて、 \(T'\) の辺 \((u_i,v_i,w_i)\) に対し、 \(T\) が \(2\) 頂点 \(u_i,v_i\) を結ぶ辺を持つことを背理法により示します。\(2\) 頂点 \(u_i,v_i\) を結ぶ辺を持たない場合、 \(T\) 上において \(u_i,v_i\) を結ぶパス \(P\) は \(2\) 本以上の辺を含みます。この問題の制約において辺の重みは \(1\) 以上であり、 \(G\) において最短経路長が \(0\) であるような \(2\) 頂点は存在しないため、 \(P\) に含まれる辺の重みは \(1\) 以上であり、 \(2\) 本以上あることからいずれも \(w_i\) 未満です。 \(P\) に含まれる辺の重みは \(G\) 上の \(2\) 頂点の最短経路長になっているため、 \(G\) 上で \(u_i,v_i\) を結ぶウォークであって、重みが \(w_i\) 未満の辺のみ用いているものが存在することが分かります。しかしこれは★の内容と矛盾しています。よって過程は誤りで、 \(T\) は \(u_i,v_i\) を結ぶ辺を持っていることがわかります。 \(T\) の条件からこの辺の重みは \(w_i\) です。

以上より \(T\) が存在する場合、 \(T=T'\) が成り立つことが分かります。これで \(T\) の候補が \(T'\) に絞れたので、あとはこれが条件を満たすかを確認すればいいです。まず \(G\) の辺で \(T'\) に含まれない辺 \((u_j,v_j,w_j)\) に着目します。 \(T'\) 上において \(u_j,v_j\) を結ぶパスの重みが \(w_j\) より大きい場合、明らかに条件を満たしません。そうでない場合、 \(G\) 以上において \(u_j,v_j\) を結ぶパスであって、 重みが \(w_j\) 以下であるものが存在するため、 \(G\) における最短経路長はこの辺を削除しても変わらないことが分かります。

\(G\) の辺で \(T'\) に含まれない辺について上記の議論ですべて削除された場合、 \(G\) の最短経路長には \(T'\) の辺しか関わらないことになります。この場合、明らかに \(T'\) は条件を満たしています。

以上により判定ができました。アルゴリズムとしては結局

• \(G\) の最小全域木 \(T'\) の構築
• \(T'\) における \(2\) 頂点を結ぶ最短パスの重みの計算を \(M-N+1\) 回

をやればいいです。前者はクラスカル法により \(O(M\alpha(N) + M\log M)\) 時間、 後者は木においてLCAを求めるアルゴリズムを用いることで \(O(M\log N)\) 時間で処理できます。