John làm việc trong một tạp chí ẩm thực. Lần này anh ta phải viết bài về các món ăn trên các chuyến bay. Bill - người sếp khó tính đã đưa cho John một danh mục \(m\) tuyến bay phải tìm hiểu. Mỗi tuyến bay này đều phục vụ ăn uống giống nhau trong cả 2 chiều, vì vậy, John không cần thiết phải đi cả 2. Trong lúc lang thang Google, John tìm thêm được \(k\) tuyến bay khác có thể có giá khuyến mãi, nhưng không được phục vụ ăn uống. John muốn tìm một hành trình đi từ thành phố \(1\) - nơi trụ sở cơ quan qua một số tuyến bay rồi trở về đúng điểm xuất phát sao cho có thể thưởng thức hết tất cả các món ăn trong các tuyến bay mà Bill đã giao. Đồng thời, công tác phí cũng eo hẹp và John cũng không có quá nhiều tiền nên nhờ bạn tìm một hành trình tiết kiệm nhất. Các thành phố và các tuyến bay có thể đi qua nhiều lần.

Input

• Dòng đầu chứa số nguyên dương \(n, m\) là số lượng thành phố và số tuyến bay mà Bill đã đưa ra (\(n \leq 13, m \leq 80\)).
• \(m\) dòng tiếp, mỗi dòng ghi \(3\) số nguyên \(a_i, b_i, c_i\) là thông tin một tuyến bay thứ \(i\) giữa \(2\) thành phố \(a_i\) và \(b_i\) với giá vé là \(c_i\).
• Dòng tiếp theo chứa số nguyên dương \(k\) (\(k \leq 200\)) là số lượng tuyến bay John đã tìm được thêm.
• \(k\) dòng cuối cùng, mỗi dòng ghi \(3\) số nguyên \(a_i, b_i, c_i\) thể hiện thông tin tuyến bay thứ \(i\) John đã tìm được (\(a_i, b_i \leq n, c_i \leq 10^4\)).

Output

• Ghi ra một số nguyên duy nhất là tổng chi phí của hành trình tìm được.

Example

5 3 
1 2 1000 
2 3 1000 
4 5 500 
2 
1 4 300 
3 5 300

3100

6 5 
1 2 1000 
2 3 1000 
1 3 1000 
2 4 1000 
5 6 500 
2 
2 5 300 
4 6 300

5100