시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
3 초 256 MB 32 7 5 20.833%

문제

Olympiland에는 1부터 N까지의 번호가 붙은 N개의 마을이 있습니다. 그들 중 일부는 서로 직접 연결되어있고, 전체 도로망은 한 도시에서 다른 도시로 가는 경로가 유일하도록 짜여져 있습니다.

거대한 기반 시설 계획을 추진하기 위해서, Ministry Council of Olympiland는 계획에 필요한 장비들을 이송하는 운송경로들을 정리해 목록을 만들었습니다. 각각의 운송경로마다 한 개의 장비만 이동됩니다. 각각의 운송경로는 양 끝 마을 u와 v (방향이 없으므로 순서를 고려하지 않아도 됩니다)로 정의되며, 이 운송경로를 따라 장비를 이동시켜서 얻는 이익 p가 있습니다.

Ministry Council은 운수 회사들을 통해 장비들을 이동시키려고 합니다. 장비의 이송 조건은 다음과 같습니다.

  • 각각의 회사는 두 개의 도시를 골라, 그 두 도시 사이의 경로(양 끝 점 포함) 상에 있는 도시들에서 시작하고 끝나는 모든 경로를 따라 장비를 이송합니다.

당신은 운수 회사의 사장이고, 가장 먼저 고를 권리가 있습니다. 그런데 당신은 사실 운수 회사를 맡기 전에는 정보 대회에서 이름깨나 떨쳤던 실력자입니다. 때문에 당신은 최선의 선택이 무엇인지를 찾는 프로그램을 만들어보고자 합니다.

입력

표준 입력의 첫 번째 줄에서는 마을의 수 N을 입력받습니다.

그 뒤의 N-1개의 줄에는 1 이상 N 이하의 서로 다른 정수 두 개가 공백으로 구분되어 주어집니다. 이 번호의 마을들은 직접 연결되어있습니다.

다음 줄은 운송경로의 수인 양의 정수 M이 주어집니다.

그 뒤의 M개의 줄은 세 개의 공백으로 구분된 양의 정수로 이루어져 있습니다: 이들은 운송경로를 나타내는 두 마을의 번호와, 그것을 처리할 때의 이득을 나타냅니다.

  • 2 ≤ N ≤ 2×105
  • 0 ≤ M ≤ 105
  • 1 ≤ 각 운송경로의 이득 ≤ 103

출력

표준 출력으로 세 개의 정수를 공백으로 구분하여 출력하세요: 최대의 이득을 얻을 수 있는 두 마을, 그리고 이 때 얻는 이득 값.

답이 여러 개 존재한다면, 임의로 하나를 출력하면 됩니다.

예제 입력

6
1 2
2 3
2 4
5 4
6 4
4
1 4 10
2 5 20
6 3 15
2 1 1

예제 출력

5 1 31

힌트

출처

Olympiad > International Tournament in Informatics > Shumen 2013 A3번

  • 잘못된 조건을 찾은 사람: koosaga
  • 문제를 번역한 사람: namnamseo