問題文

$N$ 頂点 $M$ 辺の連結かつ単純な無向グラフがあります。辺 $i$ $(1 \leq i \leq M)$ は、頂点 $U_i$ と $V_i$ を結んでいます。このグラフの上で、試練が行われます。

各頂点には、 $1$ 人ずつ人が立っています。それぞれの人は正の整数が書かれたカードを $3$ 枚ずつ持っています。頂点 $i$ $(1 \leq i \leq N)$ にいる人の持つカードに書かれている整数は $A_i, B_i, C_i$ です。

上で述べた $N$ 人に加えて、チャレンジャーであるあなたは初め頂点 $1$ にいます。あなたは他の人と同様に正の整数が書かれたカードを $3$ 枚持っています。試練は以下の手順で行われます。

• 今あなたがいる頂点に立っている人（以下、相手と呼びます）の持っているカードに書かれた整数を $A_x, B_x, C_x$ 、あなたの持っているカードに書かれた整数を $A', B', C'$ とします。$A' + B' + C' > A_x + B_x + C_x$ ならあなたの勝ち、そうでなければあなたの負けです。
• あなたが負けたなら試練は失敗となり、試練を終了します。勝ったなら、あなたは相手のカードと自分のカードをそれぞれ $1$ 枚ずつ選び、交換することができます。交換は行わなくてもよいです。そのあと、今いる頂点に隣接する好きな頂点を選び移動します。試練の過程で同じ頂点を複数回訪れてもよいです。
• 移動した先の頂点で以上のことを繰り返します。頂点 $N$ に立っている人に勝った時点で試練は成功となり、試練を終了します。

試練の過程であなた以外の人は移動しないことに注意してください。

あなたが初めに持っているカードに書かれた正の整数をそれぞれ $A, B, C$ とします。試練を成功させられる $A, B, C$ の組合せであって、$A + B + C$ が最小となるものを $1$ つ求めてください。

制約

• 入力は全て整数
• $2 \leq N \leq 10^5$
• $\displaystyle N - 1 \leq M \leq \mathrm{min} \left(\frac{N(N - 1)}{2}, 10^5 \right)$
• $1 \leq U_i, V_i \leq N$ $(1 \leq i \leq M)$
• 与えられるグラフは連結かつ単純である。(多重辺や自己ループを持たない。)
• $1 \leq A_i, B_i, C_i \leq 10^8$ $(1 \leq i \leq N)$

入力

$N$ $M$
$U_1$ $V_1$
$U_2$ $V_2$
$\vdots$
$U_{M}$ $V_{M}$
$A_1$ $B_1$ $C_1$
$A_2$ $B_2$ $C_2$
$\vdots$
$A_N$ $B_N$ $C_N$

出力

試練を成功させられる $A, B, C$ であって、 $A + B + C$ が最小であるものを以下の形式で出力せよ。答えとして考えられる $A, B, C$ の組が複数ある場合、どれを出力しても正解となる。

$A$ $B$ $C$

サンプル

サンプル1

入力

4 3
4 3
3 2
1 3
4 3 3
5 4 2
5 4 1
9 9 4

出力

1 13 1

グラフと各頂点にいる人が初め持っているカードは下図の通りです。

$A = 1, B = 13, C = 1$ としたときの手順の一例を示します。以下では、整数 $X$ の書かれたカードを単に $X$ のカードと呼びます。

初め、あなたは頂点 $1$ にいます。頂点 $1$ にいる人のカードは $4, 3, 3$ で、 $4 + 3 + 3 < 1 + 13 + 1$ よりあなたの勝ちです。

勝った後、あなたの持つ $1$ のカードのうち $1$ 枚(今回は $A$ とします) を $4$ のカードと交換します。交換した後、$A = 4, B = 13, C = 1$ です。

次に、頂点 $1$ と隣接する頂点 $3$ へ移動します。頂点 $3$ にいる人のカードは $5, 4, 1$ で、$5 + 4 + 1 < 4 + 13 + 1$ よりあなたの勝ちです。あなたの $1$ のカードを相手の $5$ のカードと交換します。交換した後、$A = 4, B = 13, C = 5$ です。

次に、頂点 $3$ と隣接する頂点 $2$ に移動します。頂点 $2$ にいる人のカードは $5, 4, 2$ で、$5 + 4 + 2 < 4 + 13 + 5$ よりあなたの勝ちです。 $4$ のカードと $5$ のカードを交換します。 $A = 5, B = 13, C = 5$ です。

次に、頂点 $3$ に戻り、頂点 $3$ にいる人に勝ちます。前に頂点 $3$ に訪れたときカードを交換したので、頂点 $3$ にいる人の持つカードは $1, 4, 1$ となっています。ここでは交換をしません。

最後に、頂点 $4$ に移動します。頂点 $4$ にいる人の持つカードは $9, 9, 4$ で、 $9 + 9 + 4 < 5 + 13 + 5$ よりあなたの勝ちです。$N = 4$ の人に勝ったので、試練は成功します。

$A + B + C < 15$ で試練を成功させる方法はありません。よって、これが正解となります。

1 1 13なども正解となります。

サンプル2

入力

3 2
1 2
2 3
1 1 1
1 1 1
100 100 100

出力

101 100 100

グラフと各頂点にいる人が初め持っているカードは下図の通りです。

$1$ 回も交換を行わなくてもよいです。

サンプル3

入力

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

出力

2 3 5

グラフと各頂点にいる人が初め持っているカードは下図の通りです。

このケースでは、1 4 5や2 4 4なども正解となります。