It is required to find in a connected graph a spanning tree of minimum weight that contains a given edge.
Input file format:
The first line of the input file contains two natural numbers N, M - the number of vertices and edges of the graph, respectively. The next m lines contain the description of the edges, one per line. The edge number i is described by three natural numbers Bi, Ei, Wi, the numbers of the ends of the edge and its weight, respectively (1 <= Bi, Ei <= N, 0 <= Wi <= 2^32-1. N <= 10, M <= 10). The last line introduces the given edge B, E, W.
Output file format:
The only line of the output file should contain one natural number - the weight of the minimum spanning tree with the given edge.
Input:
4 4
1 2 1
2 3 2
3 4 5
4 1 4
1 4 7
Output:
10