도로 위의 표지판

외판원이 된 우현이는 $1$번부터 $N$번까지 번호가 매겨진 마을을 모두 방문해야 한다. 우현이는 지금 $1$번 마을에 있다. 마을 사이에는 $M$개의 도로가 있고, 같은 두 마을을 잇는 도로는 최대 한 개다. 도로에는 두 가지 특징이 있다. 첫째, 도로마다 $1$ 이상 $9$ 이하의 숫자가 적힌 표지판이 하나씩 있다. 둘째, 도로마다 통행료가 있는데, 도로를 처음 지날 때만 낸다. 같은 도로를 다시 지나면 통행료는 들지 않는다.

우현이는 도로를 지날 때마다 그 표지판의 숫자를 핸드폰에 적는다. 입력할 때 커서를 원하는 위치에 둘 수 있으므로, "321"을 적은 상태에서 표지판 숫자가 4인 도로를 지나면 "3421"이나 "3214"를 만들 수 있다. 다만 이미 지난 적이 있는 도로의 표지판 숫자는 다시 적지 않는다.

우현이는 통행료를 내지 못하는 일은 없지만, 필요 이상으로 돈을 내고 싶지는 않다. 그래도 핸드폰에 적히는 수는 최대한 작아야 한다고 생각한다. 모든 마을을 방문하는 동안 핸드폰에 적을 수 있는 수의 최솟값과, 그 수를 적기 위해 드는 통행료의 최솟값을 구하라.

첫째 줄에 마을의 수 $N$과 도로의 수 $M$이 공백으로 구분되어 주어진다. ($1 \le N \le 200\,000$, $1 \le M \le 500\,000$)

다음 $M$개의 줄에는 도로의 정보 $x\, y\, z\, w$가 공백으로 구분되어 주어진다. 이는 $x$번 마을과 $y$번 마을이 도로로 연결되어 있고, 그 도로에는 $z$가 적힌 표지판이 있으며 통행료가 $w$원임을 뜻한다. ($1 \le x, y \le N$, $x \ne y$, $1 \le z \le 9$, $0 \le w \le 10^6$)

마을 $N$개를 전부 방문하는 것이 불가능하면 첫째 줄에 -1을 출력한다.

가능하면 첫째 줄에 마을 $N$개를 전부 방문하면서 핸드폰에 적을 수 있는 수의 최솟값과, 그 수를 적을 때 지불해야 하는 통행료의 최솟값을 공백으로 구분하여 출력한다.