파워 블로거

선영이는 음식점 리뷰를 올리는 파워 블로거이다. 몇 년 동안 매일 여러 개씩 리뷰를 써 온 덕분에, 이제 지구에 있는 모든 음식점의 리뷰를 마쳤다.

다음 차례는 기내식 리뷰다. 선영이는 사람들이 자신의 기내식 리뷰를 보고 항공편을 고르기를 기대하고 있다. 이번 리뷰는 잡지 코스모폴리탄의 다음 호에도 실릴 예정이다.

코스모폴리탄의 편집장 상근이는 선영이에게 리뷰해야 할 항공편 목록을 건네주었다. 출발 도시와 도착 도시가 같은 항공편은 모두 같은 기내식을 제공하므로, 각 항공편은 한 번만 타 보면 된다.

그런데 이 목록에 있는 항공편만으로는 모든 리뷰를 마칠 수 없다. 그래서 선영이는 항공편을 몇 개 더 예매하려 한다. 추가로 예매한 항공편의 기내식은 리뷰하지 않고, 목록에 있는 항공편만 리뷰한다.

선영이는 모든 리뷰를 마치는 데 드는 항공권 비용을 최소로 하고 싶다. 선영이의 사무실은 스톡홀롬에 있으며, 여행은 이곳에서 시작해 이곳에서 끝난다. 두 도시를 잇는 항공권의 가격은 정해져 있고 양방향 모두 같다. 모든 리뷰를 마치는 것은 항상 가능하다.

호텔 비용과 항공편의 출발·도착 시각은 무시할 수 있고, 항공편은 매우 자주 운항하며 비행 시간도 매우 짧다고 가정한다. 따라서 항공권 가격만 생각하면 된다.

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

다음 R개의 줄에는 리뷰해야 하는 항공편의 정보가 주어진다. 각 줄은 세 정수 $a$, $b$, $c$로 이루어지며, 서로 다른 두 공항 $a$, $b$를 잇는 항공권의 가격이 $c$라는 뜻이다. ($1 \le a, b \le N$, $1 \le c \le 10000$) 리뷰 목록에서 두 공항을 잇는 항공편은 많아야 하나이다.

그다음 줄에는 선영이가 추가로 이용할 수 있는 항공편의 수 F가 주어진다. ($0 \le F \le 200$) 이어지는 F개의 줄에는 같은 형식으로 항공편 정보가 주어진다. 이때는 두 공항을 잇는 항공편이 여러 개일 수도 있다.

입력으로는 항상 모든 리뷰를 마칠 수 있는 경우만 주어진다.

선영이가 모든 리뷰를 마치고 스톡홀롬으로 돌아오는 데 드는 항공권 가격의 최솟값을 출력한다.