전화 통화

바이트타운에는 $1$, $2$, $\ldots$, $n$번으로 표시된 $n$채의 집이 있다. 각 집에는 한 사람이 살고 있다. Little Q는 $1$번 집에 산다. 이 집들을 잇는 $n - 1$개의 양방향 도로가 나무 구조를 이룬다. 이 문제에서 $S (u, v)$는 $u$번 집에서 $v$번 집까지의 최단 경로 위에 있는 모든 집을 담은 집합이다.

바이트타운의 전화선 네트워크는 $m$개의 서로 다른 회선으로 구성된다. $i$번째 회선은 다섯 정수 $a\_i$, $b\_i$, $c\_i$, $d\_i$, $w\_i$로 나타내며, $S (a\_i, b\_i) \cup S (c\_i, d\_i)$에 속한 서로 다른 두 집 $u$, $v$가 $w\_i$ 달러의 비용으로 전화 통화를 할 수 있다는 뜻이다.

Little Q는 자기 집에서 큰 파티를 열 계획이고, 가능한 한 많은 사람을 초대하려 한다. 초대 소식을 아는 사람은 누구나 다른 사람에게 몇 번이든 전화를 걸어 초대를 퍼뜨릴 수 있지만, 아무도 자기 집을 떠날 수는 없다.

파티에 참여할 수 있는 사람 수의 최댓값과, 그 최댓값에 도달하기 위한 최소 총비용을 구하는 프로그램을 작성하시오. 답에는 Little Q도 포함된다.

입력의 첫째 줄에는 두 정수 $n$과 $m$이 주어진다. $n$은 집의 수, $m$은 전화선의 수이다 ($1 \leq n, m \leq 10^5$).

다음 $n - 1$개 줄에는 각각 두 정수 $u$와 $v$가 주어지며, $u$번 집과 $v$번 집 사이의 양방향 도로를 나타낸다. 집과 도로가 나무를 이룬다는 것이 보장된다.

다음 $m$개 줄 중 $i$번째 줄에는 전화선을 나타내는 다섯 정수 $a\_i$, $b\_i$, $c\_i$, $d\_i$, $w\_i$가 주어진다 ($1 \leq a\_i, b\_i, c\_i, d\_i \leq n$, $1 \leq w\_i \leq 10^9$).

한 줄에 두 정수를 출력한다. 파티에 참여할 수 있는 사람 수의 최댓값과, 그 최댓값에 도달하기 위한 최소 총비용이다.

가능한 해법 하나는 다음과 같다.

1단계: 1번 집이 1번 회선으로 2번 집에 전화를 건다. 비용은 100이다.

2단계: 1번 집이 1번 회선으로 3번 집에 전화를 건다. 비용은 100이다.

3단계: 2번 집이 2번 회선으로 4번 집에 전화를 건다. 비용은 10이다.