Minimum Cost Roads

As the newly elected mayor of Kitchener, Alanna's first job is to improve the city's road plan.

Kitchener's current road plan is a collection of $N$ intersections and $M$ roads. The $i$-th road has length $l_i$ meters, costs $c_i$ dollars per year to maintain, and connects intersections $u_i$ and $v_i$. To create a plan, Alanna must select a subset of the $M$ roads to keep and maintain. The cost of a plan is the sum of the maintenance costs of the roads in that subset.

To lower the city's annual spending, Alanna wants to minimize the plan's cost. The city also requires that travel distances stay short. Formally, for any pair of intersections $(i, j)$, if there is a path from $i$ to $j$ of length $l$ meters or less in the current road plan, then Alanna's plan must also contain a path between $i$ and $j$ of length at most $l$ meters. Any plan that breaks this rule is rejected.

The first line contains the integers $N$ and $M$.

Each of the next $M$ lines contains the integers $u_i$, $v_i$, $l_i$, and $c_i$, meaning that there is a road from intersection $u_i$ to intersection $v_i$ with length $l_i$ and cost $c_i$ $(1 \le u_i, v_i \le N, u_i \neq v_i)$.

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

$1 \le N, M \le 2\,000$

$0 \le l_i \le 10^9$

$1 \le c_i \le 10^9$