Road Construction

King Mercer rules the ACM kingdom. The kingdom has one capital and several other cities, and right now it has no roads at all. He drew up a plan to build roads between the capital and the cities, but the plan turned out to cost far more than he expected.

To cut the cost, he decided to make a new plan by removing some roads from the original one. The new plan has to satisfy both of these conditions:

• For every pair of cities there is a route of roads connecting them.
• The shortest distance from the capital to each city is the same as in the original plan.

Several plans may satisfy the conditions, and King Mercer wants the cheapest one. Write a program that reads the original plan and computes the cost of a cheapest plan that satisfies the conditions.

The input has several datasets. Each dataset has the following form.

N M
u1 v1 d1 c1
.
.
.
uM vM dM cM

The first line of a dataset has two integers, the number of cities $N$ and the number of roads in the original plan $M$ ($1 \le N \le 10000$, $0 \le M \le 20000$).

Each of the next $M$ lines describes one road of the original plan with four integers $u_i$, $v_i$, $d_i$, $c_i$ ($1 \le u_i, v_i \le N$, $u_i \ne v_i$, $1 \le d_i \le 1000$, $1 \le c_i \le 1000$). They mean that a road connects city $u_i$ and city $v_i$, its length is $d_i$, and building it costs $c_i$.

Every road is bidirectional. No two roads connect the same pair of cities. City 1 is the capital of the kingdom. In the original plan every city is reachable from the capital.

The input ends with a line holding two zeros separated by a space. Do not process that line as a dataset.

For each dataset, print the minimum cost of a plan that satisfies the conditions on one line.