Yol Tikintisi
King Mercer, ACM krallığının hökmdarıdır. Krallığında bir paytaxt və bir neçə şəhər mövcuddur. Maraqlıdır ki, hazırda krallıqda heç bir yol yoxdur. Son zamanlarda, paytaxt və şəhərlər arasında yollar inşa etməyi planlaşdırdı, lakin bu planın tikinti xərci gözləniləndən çox yüksək oldu.
Xərcləri azaltmaq üçün bəzi yolları orijinal plandan çıxararaq yeni bir tikinti planı hazırlamağa qərar verdi. Lakin, o, yeni planın aşağıdakı şərtləri təmin etməsini istəyir:
Hər bir şəhər cütü arasında onları birləşdirən bir marşrut (yollar dəsti) olmalıdır.
Paytaxt ilə hər bir şəhər arasındakı minimum məsafə orijinal planla eyni qalmalıdır.
Bu şərtlərə cavab verən bir çox plan mövcud ola bilər, lakin Kral Mercer ən az xərcli planı bilmək istəyir. Sizin vəzifəniz onun orijinal planını oxuyub minimum xərcli yeni planın xərcini hesablayan bir proqram yazmaqdır.
Giriş verilənləri
Giriş bir neçə datasetdən ibarətdir. Hər bir dataset aşağıdakı kimi formatlanır.
N M u_1 v_1 d_1 c_1 ... u_M v_M d_M c_M
Hər bir datasetin ilk sətri iki tam ədədlə, N və M (1 ≤ N ≤ 10000, 0 ≤ M ≤ 20000) başlayır. N və M müvafiq olaraq şəhərlərin və orijinal plandakı yolların sayını göstərir.
Sonrakı M sətir orijinal plandakı yol məlumatlarını təsvir edir. i-ci sətir dörd tam ədəd, u_i, v_i, d_i və c_i (1 ≤ u_i, v_i ≤ N, u_i ≠ v_i, 1 ≤ d_i ≤ 1000, 1 ≤ c_i ≤ 1000) ehtiva edir. u_i, v_i, d_i və c_i u_i-ci şəhəri və v_i-ci şəhəri birləşdirən, uzunluğu d_i olan və tikinti üçün lazım olan xərc c_i olan bir yol olduğunu göstərir.
Hər bir yol ikitərəflidir. Eyni şəhər cütünü birləşdirən iki yol yoxdur. Krallıqda 1-ci şəhər paytaxtdır.
Girişin sonu boşluqla ayrılmış iki sıfırdan ibarət bir sətirlə göstərilir. Bu sətiri dataset kimi emal etməməlisiniz.
Çıxış verilənləri
Hər bir dataset üçün şərtləri təmin edən planın minimum xərcini bir sətirdə çap edin.