도로 건설

머서 왕은 ACM 왕국의 왕이다. 왕국에는 수도 하나와 여러 도시가 있지만, 지금은 도로가 하나도 없다. 왕은 수도와 도시를 잇는 도로를 놓는 계획을 세웠는데, 그 계획대로 공사하면 비용이 예상보다 훨씬 크다는 사실을 알게 되었다.

비용을 줄이려고 왕은 원래 계획에서 도로 몇 개를 빼서 새 계획을 만들기로 했다. 다만 새 계획은 다음 두 조건을 지켜야 한다.

• 어느 두 도시를 골라도 그 둘을 잇는 경로가 있다.
• 수도에서 각 도시까지의 최단 거리가 원래 계획과 같다.

조건을 만족하는 계획은 여러 개일 수 있다. 머서 왕은 그중 비용이 가장 적은 계획을 알고 싶다. 원래 계획을 읽어서 조건을 만족하는 계획의 최소 비용을 구하는 프로그램을 작성하라.

입력은 여러 데이터 세트로 이루어진다. 각 데이터 세트의 형식은 다음과 같다.

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

각 데이터 세트의 첫 줄에는 도시의 수 $N$과 원래 계획에 있는 도로의 수 $M$이 주어진다 ($1 \le N \le 10000$, $0 \le M \le 20000$).

이어지는 $M$개의 줄에는 원래 계획의 도로 정보가 주어진다. $i$번째 줄에는 네 정수 $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$). 이는 $u_i$번 도시와 $v_i$번 도시를 잇는 길이 $d_i$, 공사 비용 $c_i$인 도로가 있다는 뜻이다.

모든 도로는 양방향이다. 같은 도시 쌍을 잇는 도로가 둘 이상 있는 경우는 없다. 1번 도시가 왕국의 수도이다. 원래 계획에서는 모든 도시가 수도에서 도달 가능하다.

입력의 끝은 공백으로 구분된 두 개의 0만 있는 줄로 표시한다. 이 줄은 데이터 세트로 처리하지 않는다.

각 데이터 세트마다 조건을 만족하는 계획의 최소 비용을 한 줄에 출력한다.