În regatul său, Balaurul nu mai este aşa iubit. Nu se ştie exact de ce. Probabil din cauza temperamentului. Cert este însă faptul că mulţi îi doresc moartea, iar cei de la Serviciul de Pază şi Protecţie au mari probleme în a asigura securitatea Majestăţii Sale Arhirel.
Regatul este compus din N oraşe numerotate de la 1 la N. Între ele există drumuri, cu sens unic. Fiecare drum are un cost pe care SPP-ul trebuie să-l plăteasca pentru a asigura securitatea pe acel drum. Capitala este oraşul numărul 1 (acolo se află şi Balaurul).
Din cauza reducerilor de buget, SPP-ul asigură securitatea doar pe traseele de la capitală la orice oraş.
Cerinţă
Ajutaţi SPP-ul să aleagă o submulţime de drumuri, astfel încât costul total de securizare al drumurilor alese să fie minim şi B.A. să poata ajunge din capitală (oraşul 1) la orice oraş, mergând numai pe drumuri securizate.
Date de intrare
Pe prima linie a fişierului spp.in se află 2 numere naturale N şi M, separate printr-un spaţiu, reprezentând numarul de oraşe şi respectiv numărul de drumuri. Pe urmatoarele M linii se află câte 3 numere separate de câte un spaţiu S D C care descriu un drum şi anume: de la oraşul S la oraşul D există un drum de cost C.
Date de ieşire
Fişierul spp.out va conţine o linie cu un singur număr întreg, costul total al securizării.
Restricţii
• 1 < N < 2 001
• 1 < M < 50 001
• 0 < costului de securizare al unui drum < 1001
• de la un oraş la altul într-un sens există maxim un drum, însă poate exista un alt drum de sens opus
• nu există drum de la un oraş la el însuşi
• tot timpul există soluţie
• 50% din teste nu vor conţine trasee care trec de două ori prin acelaşi oraş (nu există traseu de la un oraş la el însuşi)
Exemple
spp.in
spp.out
Explicaţii
4 4
1 2 13
1 3 15
2 4 14
3 4 3
31
Alegem drumurile: 1 -> 2, 1 -> 3 şi 3 -> 4.
Astfel putem ajunge din 1 in orice oras, iar costul total este minim.