Power Blogger

Sunyoung is a power blogger who posts restaurant reviews. After writing several reviews every day for years, she has now reviewed every restaurant on Earth.

Her next task is reviewing in-flight meals. Sunyoung hopes that people will choose their flights based on her in-flight meal reviews, and this round of reviews will also appear in the next issue of the magazine Cosmopolitan.

Sanggeun, the editor-in-chief of Cosmopolitan, handed Sunyoung a list of flights she must review. Every flight connecting the same pair of cities serves the same in-flight meal, so she only needs to take each such flight once.

However, the flights on this list alone are not enough to complete all the reviews. So Sunyoung plans to book a few more flights. She does not review the meals on those extra flights; she only reviews the flights on the list.

Sunyoung wants to minimize the total money spent on airplane tickets to finish all the reviews. Her office is in Stockholm, where the trip both starts and ends. The price of a ticket between two cities is fixed and is the same in both directions. It is always possible to complete all the reviews.

Hotel costs and the departure and arrival times of the flights can be ignored; assume flights run very frequently and flight times are very short. Therefore, you only need to consider ticket prices.

The first line contains the number of airports N and the number of flights to review R. Airports are numbered from 1 to N, and Stockholm is airport 1. ($2 \le N \le 13$, $0 \le R \le 78$)

Each of the next R lines describes a flight to review with three integers $a$, $b$, $c$: the ticket price between two distinct airports $a$ and $b$ is $c$. ($1 \le a, b \le N$, $1 \le c \le 10000$) In the review list there is at most one flight between any pair of airports.

The next line contains the number of additional flights F that Sunyoung may use. ($0 \le F \le 200$) Each of the following F lines gives a flight in the same format. Here there may be several flights between the same pair of airports.

Every input is guaranteed to allow all the reviews to be completed.

Print the minimum total ticket price for Sunyoung to finish all the reviews and return to Stockholm.