Minimum Cost Edge Set for Connecting Given Vertex Pairs

You are given an undirected weighted graph representing a map with cities and the roads connecting them. Each edge in the graph has a cost associated with it. In addition, you are given 4 pairs of vertices (which may contain duplicates). Your task is to select a set of edges with the minimum total cost such that, for every given pair of vertices, there exists a path between them using only the selected edges.

In other words, let \(T\) be the set of distinct vertices appearing in the 4 given pairs. You must choose a subset of edges \(E'\) such that the induced subgraph \(G' = (V, E')\) connects all the vertices in \(T\) (i.e. for any two vertices \(u, v \in T\), there exists a path from \(u\) to \(v\) in \(G'\)) and the sum of the costs of the edges in \(E'\) is minimized.

If it is impossible to connect every required vertex, output -1.

Note: Some vertices in the 4 given pairs may overlap. Also, you are allowed to use other vertices (not in \(T\)) as intermediate nodes in the connectivity.

The formula for the objective can be written in \(\LaTeX\) as:

[ \min \sum_{e \in E'} c_e \quad \text{subject to } \forall u, v \in T, ; u \leftrightarrow v \text{ in } (V, E'). ]

inputFormat

The first line contains two integers \(n\) and \(m\): the number of vertices and edges in the graph.

The next \(m\) lines each contain three integers \(u\), \(v\) and \(w\), indicating that there is an undirected edge between vertices \(u\) and \(v\) with cost \(w\).

The following 4 lines each contain two integers representing a pair of vertices that must be connected.

It is guaranteed that all vertex labels are between 1 and \(n\) (inclusive).

outputFormat

Output a single integer: the minimum total cost to connect all the given vertex pairs. If it is impossible to do so, print -1.

sample

4 3
1 2 3
2 3 4
3 4 5
1 3
2 4
1 4
4 3

12