Highway Decommission

Interview

Time limit2sMemory limit512 MB

Summary

Keep a minimum-cost subset of highays whose shortest distances to city 1 match the original graph's all-pairs distances to the capital.

Level: Medium7 of 10
Topics: Shortest path, Graph, Greedy, Heap
Solved: No attempts yet

Problem

Nlogonia's government is eager to cut down public debt. One of the measures about to take place is the decommission of some highways as most of them incur a high maintenance cost. Each highway connects two different cities and can be traveled in both directions. Using the existing highways it is possible to reach any city from any other city.

Government promises that the impact of the decommission will be minimal in the lives of Nlogonians. In particular they guarantee that after the decommission, for each city the minimum distance needed to travel from that city to the capital of the country will remain the same as it is now, when all the highways can be used.

The Department of Roads of Nlogonia believes that interns are not there just to get coffees or run errands but should do meaningful work instead and that's why you are assigned the following task. Given the length and maintenance cost of each highway, you must decide which highways will be kept active and which will be decommissioned. As you might guess, the sum of maintenance costs for the remaining highways must be minimum.

Input

The first line contains two integers N (2 ≤ N ≤ 10^4) and M (1 ≤ M ≤ 10^5), indicating respectively the number of cities and the number of highways. Cities are identified by distinct integers from 1 to N, where city 1 is the capital of Nlogonia. Each of the following M lines describes a highway with four integers A, B, L and C (1 ≤ A, B ≤ N, A ≠ B and 1 ≤ L, C ≤ 10^9), indicating that there is a highway between cities A and B that has length L and maintenance cost C. Using the existing highways it is possible to reach any city from any other city.

Output

Output a single line with an integer indicating the minimum possible sum of maintenance costs for a set of highways to be kept active. This set of highways must ensure that for each city the minimum distance needed to travel from that city to the capital of Nlogonia remains the same using only those highways.

Examples2

Example 1
Input
```
3 4
2 3 2 4
2 3 2 2
1 2 5 1
1 3 1 4
```
Expected output
```
6
```
Example 2
Input
```
2 2
1 2 10 5
2 1 6 11
```
Expected output
```
11
```