Additional Constraints 3 marks \(1 \le N, M \le 2\,000\) \(l_i = 0\) \(1 \le c_i \le 10^9\) None 6 marks \(1 \le N, M \le 2\,000\) \(1 \le l_i \le 10^9\) \(1 \le c_i \le 10^9\) There is at most one road between any unordered pair of intersections. 6 marks \(1 \le N, M \le 2\,000\) \(0 \le l_i \le 10^9\) \(1 \le c_i \le 10^9\) None

Output Specification

Output one integer, the minimum possible cost of a road plan that meets the requirements.

Sample Input

5 7
1 2 15 1
2 4 9 9
5 2 5 6
4 5 4 4
4 3 3 7
1 3 2 7
1 4 2 1

Output for Sample Input

25

Explanation of Output for Sample Input

Here is a diagram of the intersections along with a valid road plan with minimum cost.

Each edge is labeled with a pair \((l, c)\) denoting that it has length \(l\) meters and cost \(c\) dollars. Additionally, the roads that are part of the plan are highlighted, with a total cost of \(7 + 1 + 6 + 7 + 4 = 25\) .

It can be shown that we cannot create a cheaper plan that also respects the city's requirements.