問題文

NN 頂点 MM 辺の連結な単純重み付き無向グラフがあります。ii 番目の辺は、頂点ui,viu_i, v_iを結ぶ長さwiw_iの辺です。

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

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

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

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

正確には、tuple(u1,v1,w1)tuple(u_1, v_1, w_1)tuple(u2,v2,w2)tuple(u_2, v_2, w_2)について、

u1<u2u_1 < u_2 または、(u1=u2(u_1 = u_2 かつ v1<v2)v_1 < v_2) または、(u1=u2(u_1 = u_2 かつ v1=v2v_1 = v_2 かつ w1<w2)w_1 < w_2) を満たすとき、tuple(u1,v1,w1)tuple(u_1, v_1, w_1)のほうが小さい。

制約

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

入力

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

N  MN\;M
u1  v1  w1u_1\;v_1\;w_1
u2  v2  w2u_2\;v_2\;w_2
..
..
..
uM1  vM1  wM1u_{M - 1}\;v_{M - 1}\;w_{M - 1}
P1  P2  P3  P4  ...  PNP_1\;P_2\;P_3\;P_4\;...\;P_N

出力

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

u  v  wu\;v\;w

と出力してください。

入力例1
4 4
1 2 2
1 3 3
3 4 5
0 2 3 3
出力例1
1 4 3

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

入力例2
4 4
1 2 2
1 3 3
3 4 5
0 2 3 8
出力例2
1 4 8

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

提出


Go (1.21)