Problem
Se requiere encontrar en un gráfico conexo un árbol de expansión de peso mínimo que contenga una arista dada.
Formato de archivo de entrada:
La primera línea del archivo de entrada contiene dos números naturales N, M: el número de vértices y aristas del gráfico, respectivamente. Las siguientes m líneas contienen la descripción de los bordes, una por línea. El número de arista i está descrito por tres números naturales Bi, Ei, Wi, los números de los extremos de la arista y su peso, respectivamente (1 <= Bi, Ei <= N, 0 <= Wi <= 2^32-1.N <= 10, M <= 10). La última línea presenta la arista dada B, E, W.
Formato de archivo de salida:
La única línea del archivo de salida debe contener un número natural: el peso del árbol de expansión mínimo con el borde dado.
Entrada:
4 4
1 2 1
2 3 2
3 4 5
4 1 4
1 4 7
Salida:
10