Minimum Cost Edge Weight Adjustment for MST

Given a simple graph \(G=(V,E,W)\) where \(V\) is the vertex set, \(E\) is the edge set (with no multiple edges) and \(W\) is an integer weight function defined on \(E\), you are also given a spanning tree \(T\) of \(G\). You are allowed to modify the weight function \(W\) to obtain a new integer weight function \(W'\) by either increasing or decreasing the weight of any edge. Specifically, for any edge \(e\):

• If you increase its weight by \(\Delta(e)\), then \(W'(e)=W(e)+\Delta(e)\) and the cost is \(\Delta(e)\).
• If you decrease its weight by \(\Delta(e)\), then \(W'(e)=W(e)-\Delta(e)\) and the cost is \(\Delta(e)\).
• If you do not change its weight, the cost is 0.

The total modification cost is defined as \(S=\sum_{e\in E}\Delta(e)\). Your task is to choose new weights \(W'\) with minimum total cost such that the given spanning tree \(T\) becomes a Minimum Spanning Tree (MST) of \(G\). A necessary and sufficient condition for \(T\) to be an MST is that for every edge \(e\) not in \(T\), if the unique cycle created by adding \(e\) to \(T\) has a maximum weight edge \(f\) (with respect to \(W'\)), then it must hold that \(W'(e) \geq W'(f)\).

Input/Output: The graph and the tree are given in the input. You need to output the minimum total cost \(S\) required to modify \(W\) so that \(T\) becomes an MST of \(G\).

inputFormat

The input consists of the following:

1. The first line contains two integers \(n\) and \(m\) representing the number of vertices and edges respectively.
2. The next \(m\) lines each contain three integers \(u\), \(v\) and \(w\) indicating there is an edge between vertices \(u\) and \(v\) with weight \(w\).
3. The last line contains \(n-1\) distinct integers. These are the 1-indexed positions (according to the input order of the edges) of the edges that belong to the spanning tree \(T\).

outputFormat

Output a single integer denoting the minimum total cost required to modify the weights so that the given spanning tree \(T\) becomes a MST of \(G\).

sample

3 3
1 2 10
2 3 1
1 3 5
1 2

9