Manutenção do Campus
Ada trabalha na administração da MFP e está encarregada de reduzir os custos de manutenção dos caminhos do campus. O campus possui $N$ pontos de interesse e atualmente $M$ caminhos abertos conectando-os. Cada caminho tem um custo anual de manutenção.
Para cortar gastos, Ada quer interditar o máximo de caminhos possível. No entanto, há restrições:
- Alguns caminhos são oficiais: possuem sinalização permanente, iluminação especial ou fazem parte de rotas de acessibilidade. Esses caminhos não podem ser interditados.
- Após as interditações, todos os $N$ pontos devem continuar acessíveis entre si (deve existir alguma rota entre qualquer par de pontos).
- Para evitar confusão no campus, deve existir exatamente uma rota entre qualquer par de pontos, sem atalhos ou desvios alternativos.
Ada quer escolher quais caminhos manter abertos de forma a minimizar o custo total de manutenção, respeitando as restrições acima.
Se for impossível satisfazer todas as restrições (por exemplo, se os caminhos oficiais já criam uma situação em que dois pontos têm mais de uma rota entre si), imprima $-1$.
Input
A primeira linha contém três inteiros $N$, $M$ e $K$ $(2 \le N \le 2 \times 10^5,\ N-1 \le M \le 2 \times 10^6,\ 0 \le K \le M)$: número de pontos de interesse, número de caminhos atualmente abertos e número de caminhos oficiais.
As próximas $M$ linhas descrevem os caminhos. A $i$-ésima linha contém três inteiros $u_i$, $v_i$ e $w_i$ $(1 \le u_i, v_i \le N,\ u_i \ne v_i,\ 1 \le w_i \le 10^9)$: um caminho bidirecional entre os pontos $u_i$ e $v_i$ com custo de manutenção anual $w_i$.
A última linha contém $K$ inteiros distintos $e_1, e_2, \ldots, e_K$ $(1 \le e_j \le M)$: os índices dos caminhos oficiais (na ordem em que foram listados).
Output
Um único inteiro: o menor custo total de manutenção anual possível, ou $-1$ se for impossível.
4 5 1 1 2 10 1 3 1 1 4 1 2 3 1 3 4 5 1
12
Explanation 1:
O caminho $1$–$2$ (custo $10$) é oficial e não pode ser interditado. Com ele obrigatoriamente aberto, Ada ainda precisa manter abertos caminhos suficientes para conectar os pontos $3$ e $4$ sem criar rotas alternativas. A solução mais barata é manter $1$–$3$ (custo $1$) e $1$–$4$ (custo $1$). Os caminhos $2$–$3$ e $3$–$4$ são interditados. Total: $10 + 1 + 1 = \mathbf{12}$.
4 5 0 1 2 10 1 3 1 1 4 1 2 3 1 3 4 5
3
Explanation 2:
Sem caminhos oficiais, Ada pode interditar livremente. A solução mais barata que conecta tudo sem rotas alternativas mantém $1$–$3$ (custo $1$), $1$–$4$ (custo $1$) e $2$–$3$ (custo $1$). Os caminhos $1$–$2$ (custo $10$) e $3$–$4$ (custo $5$) são interditados. Total: $\mathbf{3}$.
5 6 2 1 2 3 1 3 1 2 3 4 2 4 2 3 5 5 4 5 1 1 4
7
Explanation 3:
Caminhos oficiais: $1$–$2$ (custo $3$) e $2$–$4$ (custo $2$). Com eles abertos, os pontos $3$ e $5$ ainda precisam ser conectados. Os caminhos mais baratos disponíveis são $1$–$3$ (custo $1$) e $4$–$5$ (custo $1$). Os demais são interditados. Total: $3 + 2 + 1 + 1 = \mathbf{7}$.