28473번 - 도로 위의 표지판

문제

외판원이 된 우현이는 1ドル$번부터 $N$번까지 번호가 매겨진 마을을 전부 방문하기 위해, 현재 1ドル$번 마을에 도착했다. 이곳에는 서로 다른 두 마을을 잇는 $M$개의 도로가 있으며, 두 마을 사이에는 최대 한 개의 도로가 존재한다. 이 도로들에는 몇 가지 특이한 점이 있었는데, 하나는 도로마다 중간에 1ドル$ 이상 9ドル$ 이하의 숫자가 하나 적힌 표지판이 있었다는 것이고, 하나는 도로마다 통행료를 지불해야 하는데 도로를 처음 지날 때 한 번만 돈을 지불하면 된다는 것이었다. 즉, 같은 도로를 두 번 이상 지날 때는 처음 한 번만 돈을 지불해도 되는 것이다.

숫자가 적힌 표지판이 흥미로웠던 우현이는 도로를 지날 때마다 그 숫자를 핸드폰에 적어 두려고 한다. 핸드폰에 숫자를 적을 때는 커서를 원하는 곳에 두고 적을 수 있다. 즉, 현재 “321”을 써 두었고 표지판에 ‘4’가 써 있는 도로를 지났다면 “3421”, “3214” 등의 수를 만들 수 있다. 그러나 이미 지난 적이 있는 도로의 표지판 숫자는 다시 적지 않기로 했다.

그리고 돈이 많은 우현이는 통행료를 내지 못하는 경우는 없었지만, 당연히 불필요하게 돈을 더 지불하고 싶지는 않았다. 하지만 우현이는 핸드폰에 적을 수 있는 수의 최솟값이 얼마인지 궁금해졌고, 돈을 조금 더 지불하더라도 최대한 작은 수를 적고 싶었다. 우현이가 $N$개의 마을을 전부 방문하는 동안 핸드폰에 적을 수 있는 수의 최솟값을 구하고, 그 수를 만들기 위해서 들어가는 비용의 최솟값을 구하는 프로그램을 작성하자.

입력

첫째 줄에 마을의 수 $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$개를 전부 방문하는 것이 가능하다면, 첫째 줄에 마을 $N$개를 전부 방문할 때 핸드폰에 적을 수 있는 수의 최솟값과, 그때 지불해야 하는 비용의 최솟값을 공백으로 구분하여 출력한다.

제한

힌트