개의 정점으로 이루어진 트리가 주어진다. 트리의 정점에는 번부터 번까지 번호가 붙어 있으며, 그 중 번 정점이 루트이다.
당신은 처음에 번 정점에 있으며, 트리의 모든 정점을 적어도 한 번씩 방문한 뒤 다시 번 정점으로 돌아오려고 한다.
트리의 간선을 따라 이동할 때에는 부모 정점에서 자식 정점으로만 이동할 수 있다. 즉, 자식 정점에서 부모 정점으로 간선을 따라 이동하는 것은 불가능하다.
대신, 몇몇 정점에는 그 정점의 조상 정점으로 이동할 수 있는 포탈을 설치할 수 있다. 포탈을 설치하려면 정해진 비용을 지불해야 하며, 한 번 설치한 포탈은 순회 도중 원하는 만큼 여러 번 사용할 수 있다.
설치할 수 있는 포탈의 종류가 개 주어진다. 각 포탈은 특정 정점에서 출발하여 그 정점의 특정한 조상 정점으로 이동한다.
주어진 포탈들 중 일부를 선택하여 설치했을 때, 모든 정점을 적어도 한 번씩 방문하고 다시 번 정점으로 돌아오는 것이 가능하도록 하는 포탈 설치 비용의 최솟값을 구해 보자.
첫 번째 줄에 정점의 수 과 설치할 수 있는 포탈의 종류의 수 이 공백으로 구분되어 주어진다.
두 번째 줄부터 개의 줄에는 트리의 간선 정보가 주어진다. 그 중 번째 줄에는 두 정수 , 가 공백으로 구분되어 주어지며, 이는 번 정점과 번 정점이 간선으로 연결되어 있음을 의미한다.
조건을 만족하는 순회를 가능하게 하기 위해 필요한 포탈 설치 비용의 최솟값을 출력한다.
어떤 포탈들을 설치하더라도 조건을 만족하는 순회가 불가능하다면 -1을 출력한다.
;
다음 개의 줄에는 설치할 수 있는 포탈의 정보가 주어진다. 그 중 번째 줄에는 세 정수 , , 가 공백으로 구분되어 주어진다. 이는 번 정점에서 출발하여 번 정점으로 이동하는 포탈을 비용 에 설치할 수 있음을 의미한다. 는 항상 의 조상 정점이다.
;
