고속도로 해체

면접 대비

시간 제한2초메모리 제한512 MB

요약

모든 도시에서 수도로 가는 최단 거리를 원래와 같게 유지하면서 유지비 합이 최소인 고속도로 집합을 고른다.

난이도: 보통10점 중 7점
유형: 최단 경로, 그래프, 그리디, 힙
정답자: 아직 제출이 없습니다

문제

Nlogonia 정부는 공공 부채를 줄이려고 한다. 곧 시행될 조치 중 하나는 유지비가 많이 드는 고속도로 일부를 해체하는 것이다. 각 고속도로는 서로 다른 두 도시를 연결하며 양방향으로 통행할 수 있다. 현재 있는 고속도로를 이용하면 어느 도시에서든 다른 도시로 갈 수 있다.

정부는 해체가 Nlogonia 주민의 생활에 미치는 영향이 최소가 될 것이라고 약속한다. 특히 해체 후에도 모든 고속도로를 사용할 수 있을 때와 비교해 각 도시에서 수도까지 가는 데 필요한 최소 거리가 그대로 유지된다고 보장한다.

Nlogonia 도로부는 인턴이 커피를 사 오거나 심부름을 하는 자리가 아니라 의미 있는 일을 해야 하는 자리라고 생각한다. 그래서 당신에게 다음 임무가 주어졌다. 각 고속도로의 길이와 유지비가 주어질 때, 어떤 고속도로를 계속 사용하고 어떤 고속도로를 해체할지 정해야 한다. 짐작하겠지만 남는 고속도로의 유지비 합은 최소여야 한다.

입력

첫째 줄에 도시의 수 N (2 ≤ N ≤ 10^4)과 고속도로의 수 M (1 ≤ M ≤ 10^5)이 주어진다. 도시는 1부터 N까지의 서로 다른 정수로 구분하며, 도시 1은 Nlogonia의 수도다. 다음 M개 줄에 각각 고속도로를 나타내는 네 정수 A, B, L, C (1 ≤ A, B ≤ N, A ≠ B, 1 ≤ L, C ≤ 10^9)가 주어진다. 이는 도시 A와 B 사이에 길이 L, 유지비 C인 고속도로가 있음을 뜻한다. 현재 있는 고속도로를 이용하면 어느 도시에서든 다른 도시로 갈 수 있다.

출력

계속 사용할 고속도로 집합의 유지비 합으로 가능한 최솟값을 한 줄에 정수로 출력한다. 이 고속도로 집합만 이용해도 각 도시에서 Nlogonia의 수도까지 가는 데 필요한 최소 거리는 그대로여야 한다.

예제2

예제 1
입력
```
3 4
2 3 2 4
2 3 2 2
1 2 5 1
1 3 1 4
```
예상 출력
```
6
```
예제 2
입력
```
2 2
1 2 10 5
2 1 6 11
```
예상 출력
```
11
```