Signs on the Road

Woohyeon became a traveling salesman and needs to visit every town numbered from $1$ to $N$. He is currently in town $1$. There are $M$ roads between the towns, and any two towns are connected by at most one road. Each road has two properties. First, each road has a sign with a digit from $1$ to $9$. Second, each road has a toll, but the toll is paid only the first time the road is crossed. Crossing the same road again costs nothing.

Whenever Woohyeon crosses a road, he writes the digit on its sign on his phone. He can place the cursor anywhere before typing, so after writing "321" and crossing a road with a 4 sign, he can produce "3421" or "3214". However, he does not write the digit of a road he has already crossed.

Woohyeon never lacks the money for a toll, but he does not want to pay more than necessary. Still, he wants the number on his phone to be as small as possible, even if that costs a little more. Find the smallest number he can write on his phone while visiting all $N$ towns, and the minimum toll needed to write that number.

The first line contains $N$ and $M$, separated by a space. ($1 \le N \le 200\,000$, $1 \le M \le 500\,000$)

Each of the next $M$ lines contains $x\, y\, z\, w$, separated by spaces. This means towns $x$ and $y$ are connected by a road with sign $z$, and its toll is $w$ won. ($1 \le x, y \le N$, $x \ne y$, $1 \le z \le 9$, $0 \le w \le 10^6$)

If it is impossible to visit all $N$ towns, print -1 on the first line.

If it is possible, print on the first line the smallest number that can be written on the phone while visiting all $N$ towns, and the minimum toll needed to write that number, separated by a space.