Problem
È necessario trovare in un grafo connesso uno spanning tree di peso minimo che contenga un dato arco.
Formato del file di input:
La prima riga del file di input contiene due numeri naturali N, M, rispettivamente il numero dei vertici e degli spigoli del grafico. Le m righe successive contengono la descrizione dei bordi, uno per riga. Il numero dello spigolo i è descritto da tre numeri naturali Bi, Ei, Wi, rispettivamente i numeri delle estremità dello spigolo e il suo peso (1 <= Bi, Ei <= N, 0 <= Wi <= 2^32-1. N <= 10, M <= 10). L'ultima riga introduce il dato arco B, E, W.
Formato del file di output:
L'unica riga del file di output deve contenere un numero naturale: il peso dell'albero di copertura minimo con il dato bordo.
Inserimento:
4 4
1 2 1
2 3 2
3 4 5
4 1 4
1 4 7
Uscita:
10