Minimum Modification Cost for Spanning Tree

Given a connected undirected weighted graph with m edges and n vertices. For each edge i the original weight is \(w_i\). You are allowed to change the weight of an edge. Increasing the weight by 1 costs \(a_i\) and decreasing it by 1 costs \(b_i\).

You are also given a spanning tree \(T\) of the graph (specified by the indices of its n-1 edges). Your task is to modify the edge weights (possibly both in the spanning tree and outside it) such that the given spanning tree \(T\) becomes a minimum spanning tree (MST) of the modified graph. In other words, after the modifications, for every edge \(e\) that is not in \(T\), if we denote by \(P_e\) the unique path in \(T\) connecting the endpoints of \(e\) and let \(M_e = \max_{f \in P_e} x_f\) (where \(x_f\) is the new weight of tree edge \(f\)), then we must have

[ x_e \geq M_e. ]

The total cost of modifications is computed as follows. For each edge \(i\), if you change its weight from \(w_i\) to \(x_i\), the cost incurred is:

[ \text{cost}_i = \begin{cases} a_i \times (x_i - w_i), & \text{if } x_i \ge w_i,\ b_i \times (w_i - x_i), & \text{if } x_i < w_i. \end{cases} ]

Your goal is to achieve the MST property for \(T\) with the minimum total cost.

Note: It is allowed for the modified edge weights to be equal; in such cases, if \(T\) is one of the MSTs then it is acceptable.

inputFormat

The first line contains two integers \(n\) and \(m\) \((2 \le n \le 2000,\ n-1 \le m \le 10000)\) representing the number of vertices and edges.

Then follow m lines. The \(i\)-th of these lines contains five integers \(u_i, v_i, w_i, a_i, b_i\) \((1 \le u_i,v_i \le n)\). This means that there is an undirected edge between vertices \(u_i\) and \(v_i\) with original weight \(w_i\), increasing cost \(a_i\) and decreasing cost \(b_i\).

The last line contains n-1 distinct integers between 1 and \(m\) (inclusive) specifying the indices of the edges that form the given spanning tree \(T\). The edges are 1-indexed in the order they appear in the input.

outputFormat

Output a single integer --- the minimum total cost required so that after modifying the edge weights the spanning tree \(T\) becomes an MST of the graph.

sample

2 1
1 2 10 5 5
1

0