시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
3 초 256 MB 21 4 2 15.385%

문제

There are N towns in Olympiland, numerated with the integers from 1 to N. Some of them are directly connected and the road network is organized in a way that there is only one possible path from any town to any other one, which may not be direct, but passing through other towns. For accomplishing a big infrastructure project the Ministry Council of Olympiland created a list of routes to transport the equipment needed for the project. Only one equipment transportation will be executed along each route. One route is defined by two towns u and v, between which the equipment will be transported (never mind in what direction) and a profit p realized by the company which will make the transportation along this route. The Ministry Council initializes a contest among the transportation companies in the country for accomplishing the shipping along the routes. The condition is: each company to choose two towns and to accomplish the equipment transportation along all listed routes which start and end on the way between the two selected towns (inclusively). You are the president of a transporting company and have the right to choose first. As you, by the way, happen to be a competitor in informatics, you can do the best choice by writing a program profit to pick out two towns in Olympiland so that your company will derive maximal benefit from serving the routes lying on the way between the two selected towns.

입력

From the first line of the standard input is read the positive integer N – the number of the towns in Olymliland.

Each of the next N-1 lines contains two different space separated positive integers not greater an N – the couples of towns, which are directly connected by road.

The next line contains the positive integer M – the length of the transportation routes list.

Each of the next M lines contains three space separated positive integers: the numbers of the two towns, defining the route, and the profit of its realization.

2 ≤ N ≤ 2×105 ; 0 ≤ M ≤ 105 ; 1 ≤ each route profit ≤ 103.

출력

Write to the standard output three space separated integers: the numbers of two towns, leading to the maximal profit from serving the routes between them, followed by the value of the maximal profit itself. If there exist more than one solution, output one arbitrary chosen.

예제 입력

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