Problem Statement

You are given a simple undirected connected graph with $N$ vertices and $M$ edges. The $i$-th edge connects vertex $u_i$ and vertex $v_i$, and its length is the irreducible fraction $\dfrac{a_i}{b_i}$. For each $i=2,...,N$, output the shortest distance from vertex $1$ as an irreducible fraction.

Input

The input is given from standard input in the following format.

$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$
• The given graph is simple and connected.
• $\text{gcd}(a_i,b_i)=1$
• All input values are integers.

Output

Output $N-1$ lines. On the $i$-th line, when the shortest distance to vertex $i+1$ is represented by the irreducible fraction $\dfrac{c}{d}$, output it in the following format.

$c$ $d$

Print a newline at the end.

Sample

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