파워 블로거

선영이는 블로그에 음식점 리뷰를 올리는 파워 블로거이다. 음식점 리뷰를 몇 년동안 하루에 몇 개씩 하다보니, 이제 지구에 있는 모든 음식점의 리뷰를 작성했다.

이제, 기내식 리뷰를 작성할 차례이다. 선영이는 사람들이 자신의 기내식 리뷰를 보고 항공편을 고르는 효과를 기대하고 있다.

이번 기내식 리뷰는 코스모폴리탄 다음 호에도 올라갈 예정이다. 코스모폴리탄의 편집장인 상근이는 선영이에게 기내식 리뷰를 해야하는 항공편 리스트를 주었다. 선영이는 출발과 도착 도시가 같은 각 항공편은 같은 기내식을 제공한다는 사실을 알고 있다. 따라서, 한 번만 타면 된다.

상근이가 준 리스트에 있는 항공편만 이용해서는 모든 리뷰를 할 수 없다. 따라서, 선영이는 비행기를 조금 더 예매하려고 한다. 이렇게 예매를 한 비행기의 기내식은 리뷰를 하지 않고, 리스트에 있는 기내식만 리뷰를 한다.

선영이는 모든 리뷰를 작성하면서 드는 비행기 티켓에 쓰는 돈을 최소로 하려고 한다. 선영이의 사무실은 스톡홀롬에 있고, 이 곳에서 여행이 시작되고 끝이 난다. 두 도시를 운항하는 비행기 티켓의 가격은 고정되어 있으며, 양방향 모두 같다. 항상 모든 리뷰를 완료하는 것이 가능하다.

선영이가 이용하는 호텔의 비용, 비행기의 출발과 도착 시간은 무시할 수 있고, 비행기는 매우 자주 운항하며 비행 시간은 매우 작다고 가정한다. 따라서, 비행기 티켓의 가격만 생각하고 문제를 풀면 된다.

첫째 줄에 N과 R이 주어진다. N은 공항의 수, R은 리뷰를 작성해야 하는 항공편의 수이다. 공항은 1부터 N까지 번호가 매겨져 있고, 스톡홀롬의 번호는 1이다. (2 ≤ N ≤ 13, 0 ≤ R ≤ 78)

다음 R개 줄에는 리뷰를 작성해야 하는 항공편의 정보이다. 각 줄은 3개의 정수 a, b, c로 이루어져 있으며, a와 b는 서로 다른 두 공항을, c는 비행기 티켓 가격이다. (1 ≤ a, b ≤ N, 1 ≤ c ≤ 10,000) 두 도시를 운항하는 비행기의 수는 한 개를 넘지 않는다.

다음 줄에는 선영이가 추가적으로 이용할 수 있는 항공편의 수 F가 주어진다. (0 ≤ F ≤ 200) 다음 F개 줄에는 위와 같은 형식으로 정보가 주어진다. 두 도시를 운항하는 비행기의 수가 여러 개일 수도 있다.

항상 리뷰를 모두 작성할 수 있는 경우만 입력으로 주어진다.

선영이가 모든 리뷰를 작성하고 스톡홀롬으로 돌아오는데 드는 비행기 티켓의 값의 최솟값을 출력한다.