최소 비용 도로

새로 선출된 키치너 시장 Alanna의 첫 업무는 도시의 도로 계획을 개선하는 것이다.

키치너의 현재 도로 계획은 $N$개의 교차로와 $M$개의 도로로 이루어져 있다. $i$번째 도로의 길이는 $l_i$미터이고, 연간 유지비는 $c_i$달러이며, 교차로 $u_i$와 $v_i$를 잇는다. 계획을 세우려면 Alanna가 $M$개의 도로 중 일부를 골라 유지해야 한다. 계획의 비용은 선택한 도로들의 유지비를 모두 더한 값이다.

Alanna는 도시의 연간 지출을 줄이기 위해 계획의 비용을 최소화하려고 한다. 도시는 또한 이동 거리가 짧기를 요구한다. 형식적으로 말하면, 임의의 교차로 쌍 $(i, j)$에 대해 현재 도로 계획에서 $i$에서 $j$로 가는 길이가 $l$미터 이하인 경로가 존재하면, Alanna의 계획에도 $i$와 $j$를 잇는 길이 $l$미터 이하의 경로가 있어야 한다. 이 규칙을 어기는 계획은 거부된다.

첫 줄에 정수 $N$과 $M$이 주어진다.

다음 $M$개의 줄에는 정수 $u_i$, $v_i$, $l_i$, $c_i$가 주어지며, 이는 교차로 $u_i$에서 교차로 $v_i$로 가는 길이 $l_i$, 비용 $c_i$의 도로가 있다는 뜻이다 $(1 \le u_i, v_i \le N, u_i \neq v_i)$.

요구 조건을 만족하는 도로 계획의 최소 비용을 정수 하나로 출력한다.

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

$0 \le l_i \le 10^9$

$1 \le c_i \le 10^9$