Різнокольоровий каркас
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) | Output (stdout) |
|---|---|
| 4 3 4 3 17 3 1 7 2 3 16 3 2 4 13 1 3 4 1 2 5 | 20 |
Submit a solution
| Element Type | Created | Who | Problem | Compiler | Result | Time (sec.) | Memory (MiB) | # | Actions |
|---|
| Element Type | Created | Who | Problem | Compiler | Result | Time (sec.) | Memory (MiB) | # | Actions |
|---|