ALGO 시에는 $N$ 개의 교차로와 $M$ 개의 도로가 있습니다. $i$ 번째 도로는 교차로 $A_i$ 와 $B_i$ 를 양방향으로 연결하며 길이는 $C_i$ 미터입니다. 어떤 교차로에서든 다른 교차로로 반드시 이동할 수 있음이 보장됩니다. 또한 $D_i = 1$ 인 도로에는 나무가 한 그루 심어져 있습니다.
ALGO 시의 시장인 지로 군은 교차로 1과 교차로 $N$ 을 잇는 마라톤 코스를 만들기로 했습니다. 그는 참가자들을 힘들게 하고 싶지 않아 총 거리를 가능한 짧게 하고 싶습니다. 또한 참가자들이 자연을 즐기길 원하므로, 총 거리가 같을 경우 코스에 심어진 나무의 수를 더 많게 하고 싶습니다. 어떤 코스가 가장 좋겠습니까?

[제약 조건]
• $2 \le N \le 8{,}000$
• $1 \le M \le 100{,}000$
• $1 \le C_i \le 100$
• 모든 교차점 사이에는, 몇 가지 도로를 통해 반드시 왕래할 수 있음이 보장됩니다.
• $1 \le A_i < B_i \le N$
• $i \neq j$ 이면 $(A_i, B_i) \neq (A_j, B_j)$
• $D_i$ 는 $0$ 또는 $1$ 입니다.

첫째 줄에 $N, M$ 이 주어집니다.
둘째 줄부터 $M$ 개의 줄에 걸쳐 도로 정보 $A_i, B_i, C_i, D_i$ 가 주어집니다.

최단 경로의 길이와 그때의 최대 나무 수를 공백으로 구분하여 출력하세요.

3 3
1 2 70 1
2 3 20 1
1 3 90 0

90 2