Anti-Dijikstra

問題文

$N$ 頂点 $M$ 辺の連結な単純重み付き無向グラフがあります。$i$ 番目の辺は、頂点$u_i, v_i$を結ぶ長さ$w_i$の辺です。

ダイクストラさんは、ダイクストラ法を用いて頂点 $1$ から $k = 1,2,3...N$ までの最短距離 $P_1, P_2, ... P_N$ を求めました。

その後、ダイクストラさんのアンチであるつばきくんはこのグラフから一つ辺を取り除いてしまいました。

つばきくんが取り除いてしまった可能性がある辺のうち、以下の条件を満たすものを出力してください。

• つばきくんが辺を取り除いたあとのグラフに、求めた辺を追加したグラフの頂点 $1$ から $k = 1,2,3...N$ までの最短距離がダイクストラさんが求めたものに等しい
• 頂点u, vを結ぶ長さwの辺として、$tuple(u, v, w)$の小さい順に並べたときの最小のもの。

正確には、$tuple(u_1, v_1, w_1)$ と $tuple(u_2, v_2, w_2)$について、

$u_1 < u_2$ または、$(u_1 = u_2$ かつ $v_1 < v_2)$ または、$(u_1 = u_2$ かつ $v_1 = v_2$ かつ $w_1 < w_2)$ を満たすとき、$tuple(u_1, v_1, w_1)$のほうが小さい。

制約

• $2 \leq N \leq 10^5$
• $N - 1 \leq M \leq min(10^5, N \times (N - 1) / 2)$
• $0 < w \leq 10^9$
• $1 \leq u_i < v_i\leq N\;(0 < i \leq M)$
• 入力はすべて整数
• 条件を満たす辺が必ず一つ以上存在する。

入力

一行目に、$N, M$ が空白区切りで与えられます。次の$M - 1$ 行ではつばき君が元のグラフから取り除いた辺以外の辺が与えられます。 最後に、ダイクストラさんが元のグラフで求めた最短距離が空白区切りで与えられます。

出力

条件を満たす辺が頂点$u, v$ を結ぶ長さ$w$ の辺であるとき、空白区切りで

$u\;v\;w$

と出力してください。

例

4 4
1 2 2
1 3 3
3 4 5
0 2 3 3

1 4 3

つばきくんが辺を取り除いた後のグラフ上では1から4の距離が8になっているため、1と4を結ぶ長さ3の辺を追加すれば辻褄が合います。

4 4
1 2 2
1 3 3
3 4 5
0 2 3 8

1 4 8

つばきくんが辺を取り除く前のグラフに多重辺が存在していないことに注意してください。