Різнокольоровий каркас

Limits: 2 sec., 256 MiB

Вам дано зв’язний неорієнтований зважений граф з \(n\) вершин. Кожне з його \(m\) ребер пофарбоване в один з двох кольорів — червоний або синій.

Вартістю каркаса цього графу, що містить ребра обох кольорів, назвемо суму ваг найважчого червоного та найважчого синього ребер.

Потрібно знайти каркас з мінімальною вартістю.

Input

У першому рядку задано ціле число \(n\) — кількість вершин у графі.

У другому рядку задано ціле число \(r\) — кількість червоних ребер у графі.

Далі в кожному з наступних \(r\) рядків описано ребра червоного кольору у форматі \(u_i\), \(v_i\), \(w_i\) — кінці ребра та його вага.

У наступному рядку задано ціле число \(b\) — кількість синіх ребер у графі.

У наступних \(b\) рядках описано ребра синього кольору у вищенаведеному форматі.

Output

Виведіть ціле число — мінімально можливу вартість каркасу з принаймні одним синім та принаймні одним червоним ребром. Якщо такого немає, виведіть -1.

Constraints

\(3 \le n \le 400\),

\(2 \le m \le 10^5\),

\(r + b = m\),

\(1 \le u_i, v_i \le n\),

\(1 \le w_i \le 10^6\).

Samples

Input (stdin) сopy	Output (stdout) сopy
4 3 4 3 17 3 1 7 2 3 16 3 2 4 13 1 3 4 1 2 5	20