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

Обмеження: 2 сек., 256 МіБ

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

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

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

Вхідні дані

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

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

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

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

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

Вихідні дані

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

Обмеження

\(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\).

Приклади

Вхідні дані (stdin) копіювати	Вихідні дані (stdout) копіювати
4 3 4 3 17 3 1 7 2 3 16 3 2 4 13 1 3 4 1 2 5	20