A Nlogônia inaugurou um moderno complexo de laboratórios
subterrâneos de pesquisa, interligando múltiplos centros de
estudo localizados em diferentes cidades. Para permitir a transferência
de pesquisadores, equipamentos e amostras, foi construída uma rede mista
de túneis subterrâneos e pontes
suspensas que conectam pares de cidades.
Neste momento, é possível, eventualmente fazendo baldeações, alcançar
qualquer centro a partir de outro por meio de rotas já existentes.
Entretanto, o comitê de ciência deseja modernizar a infraestrutura,
escolhendo para isso um conjunto de túneis e pontes a serem
reformados.
Como o orçamento é limitado, nem todos poderão ser contemplados ao mesmo
tempo. O plano de reforma deve obedecer estes critérios:
- No final, deve ser possível viajar entre qualquer par de cidades
usando só túneis e pontes reformadas (a rede reformada deve ser
conexa!);
- A prioridade é minimizar o número de pontes
reformadas — já que a passagem por túneis é considerada mais
segura;
- Entre as escolhas possíveis, minimize o custo total
da reforma.
Você deve, ao receber os custos das reformas de cada túnel e ponte,
determinar o menor custo total possível do plano final,
respeitando os critérios acima.
Entrada
- A primeira linha contém três inteiros
,
,
,
que representam o número de cidades, o número de túneis disponíveis e o
número de pontes.
- As
linhas seguintes descrevem cada túnel, com três inteiros
,
,
(
e
são cidades,
é o custo da reforma deste túnel).
- As
linhas finais descrevem as pontes, cada uma com três inteiros
,
,
(
e
são cidades,
é o custo da reforma desta ponte).
Saída
- Imprima na única linha o menor custo possível para
o plano de reforma, de acordo com as prioridades acima.
Restrições
-
e
- ,
- ,
Exemplos
Exemplo de entrada 1
3 3 2
1 2 1000
1 3 1000
2 3 900
1 3 800
2 3 700
Exemplo de saída 1
1900