슬로프에 스키어 배치하기

스키어들의 단체 여행을 준비하려고 한다. 스키어들은 하루 동안 빌린 큰 산으로 여행을 떠난다.

산에는 1부터 N까지 번호가 매겨진 N개의 휴게 지점이 있으며, 이들은 N-1개의 슬로프로 연결되어 있다. 각 슬로프는 어떤 휴게 지점에서 시작하여 중간에 다른 슬로프나 휴게 지점을 거치지 않고 다른 휴게 지점으로 곧장 이어진다. 슬로프는 한 방향으로만 이동할 수 있다.

각 스키어는 정상 휴게 지점에서 출발하여 슬로프를 타고 다른 휴게 지점에 도착한다. 그곳에서 다시 다른 슬로프를 타고 또 다른 휴게 지점에 도착하는 식으로 이동할 수 있다. 스키어가 목적지 휴게 지점에 도착하면 그날의 스키를 마치고 따뜻한 코코아를 마시러 스키 산장으로 향한다. 목적지 휴게 지점은 정상 휴게 지점일 수 없다. 다만 스키어의 목적지 휴게 지점에서 시작하는 슬로프가 없거나 여러 개일 수도 있다는 점에 유의하라. 즉, 이용할 수 있는 슬로프가 하나도 남지 않을 때까지 반드시 계속 슬로프를 이용해야 하는 것은 아니다. 언제든지 남은 산길을 조심스럽게 걸어 내려갈 수 있다! 모든 휴게 지점에 대해, 스키어가 정상 휴게 지점에서 그곳에 도달하는 데 이용할 수 있는 슬로프의 순서는 정확히 하나이다.

각 슬로프는 하루 동안 수용할 수 있는 스키어의 총수가 정해져 있으며, 그 수를 넘으면 눈이 너무 울퉁불퉁해져 스키를 탈 수 없다. 또한 스키장은 각 스키어가 타는 각 슬로프에 대해 요금을 부과하거나 보상금을 지급할 수 있다. 슬로프마다 요금이 다를 수 있으며, 각 스키어는 자신이 타는 각 슬로프의 요금을 지불해야 한다. 슬로프의 요금은 양수, 영 또는 음수일 수 있다. 음수인 요금은 해당 슬로프를 시험한 대가로 지급되는 현상금을 뜻한다. 주최자인 당신은 스키어 단체를 대신하여 모든 슬로프 요금을 지불하고 모든 현상금을 받는다. 여러 스키어가 같은 슬로프를 이용하면 그 슬로프의 요금을 여러 번 지불하거나 현상금을 여러 번 받는다는 점에 유의하라. 지불한 모든 비용의 합에서 받은 모든 현상금의 합을 뺀 값이 여행의 총지출이다. 지출은 양수, 영 또는 음수일 수 있다. 지출이 음수라면 여행에서 실제로 돈을 벌었다는 뜻이다!

주최자로서 산에 배치할 수 있는 스키어 수의 최댓값을 구하려고 한다. 또한 그 최대 인원의 스키어가 여행할 때 가능한 최소 지출도 구하려고 한다.

제한

시간 제한: 테스트 세트당 30초. 메모리 제한: 1GB. 모든 i에 대해, 1 ≤ $U_{i}$ ≤ N. 모든 i에 대해, 2 ≤ $V_{i}$ ≤ N. (어떤 슬로프도 정상 휴게 지점에서 끝날 수 없다.) 모든 i에 대해, $U_{i}$ ≠ $V_{i}$. 모든 i에 대해, 1 ≤ $S_{i}$ ≤ $10^{5}$. 모든 i에 대해, -$10^{5}$ ≤ $C_{i}$ ≤ $10^{5}$. 모든 r에 대해, 스키어가 정상 휴게 지점에서 휴게 지점 r에 도달하는 데 이용할 수 있는 슬로프의 순서는 정확히 하나이다.

테스트 세트 1 (공개 판정)

1 ≤ T ≤ 100. 2 ≤ N ≤ 1000.

테스트 세트 2 (비공개 판정)

T = 17. 2 ≤ N ≤ $10^{5}$.

입력의 첫 줄에는 테스트 케이스의 수 T가 주어진다. 이어서 T개의 테스트 케이스가 주어진다. 각 테스트 케이스의 첫 줄에는 산에 있는 휴게 지점의 수를 나타내는 정수 N 하나가 주어진다.

각 테스트 케이스의 마지막 N-1개 줄에는 각각 네 정수 $U_{i}$, $V_{i}$, $S_{i}$, $C_{i}$으로 슬로프 하나가 설명된다. 이들은 각각 슬로프의 시작 휴게 지점, 끝 휴게 지점, 슬로프가 수용할 수 있는 최대 스키어 수, 스키어 한 명당 슬로프 요금이다.

스키어들이 출발하는 정상 휴게 지점의 번호는 항상 1이다.

각 테스트 케이스마다 Case #x: y z을 포함하는 한 줄을 출력한다. 여기서 x는 1부터 시작하는 테스트 케이스 번호이고, y는 스키어 수의 최댓값이며, z는 y명의 스키어가 각자 적어도 하나의 슬로프를 탈 때의 최소 지출이다.

예제 케이스 #1에서는 스키어 한 명을 휴게 지점 4로, 스키어 한 명을 휴게 지점 3로, 스키어 두 명을 휴게 지점 2로 보낼 수 있다.

예제 케이스 #2에서는 스키어 세 명을 휴게 지점 2로, 스키어 두 명을 휴게 지점 5로, 스키어 두 명을 휴게 지점 4로 보낼 수 있다.

테스트 케이스에 처음 나열된 슬로프가 반드시 정상 휴게 지점에서 시작할 필요는 없으며, 슬로프에서 $U_{i}$ > $V_{i}$일 수 있다는 점에 유의하라.