問題文

$N$ 頂点 $M$ 辺の単純無向連結グラフが与えられます。 $i$ 番目の辺は頂点 $u_i$ と頂点 $v_i$ を結んでおり、長さは既約分数 $\dfrac{a_i}{b_i}$ です。 $i=2,...,N$ について、頂点 $1$ からの最短距離を既約分数で出力してください。

入力

入力は以下の形式で標準入力から与えられます。

$N\ M$
$u_1\ v_1\ a_1\ b_1$
$\vdots$
$u_M\ v_M\ a_M\ b_M$

• $2\leq N\leq 3\times 10^4$
• $N-1\leq M\leq \min(5\times 10^4, N(N-1)/2)$
• $1\leq u_i, v_i\leq N$
• $1\leq a_i, b_i\leq 300$
• 与えられるグラフは単純かつ連結
• $\text{gcd}(a_i,b_i)=1$
• 入力はすべて整数

出力

$N-1$ 行出力してください。 $i$ 行目は、頂点 $i+1$ までの最短距離が既約分数 $\dfrac{c}{d}$ で表されるとき、以下の形式で出力してください。

$c$ $d$

最後に改行してください。

サンプル

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

3 2
1 2
7 2

8 10
2 3 2 3
1 5 5 4
6 8 10 9
1 8 8 13
1 2 9 17
3 6 86 79
1 4 9 1
5 7 2 5
1 6 2 3
6 7 3 2

9 17
61 51
9 1
5 4
2 3
33 20
8 13