Stelele Informaticii 2024 - Mirror Day 2 | Primăvara lui '03

Ernő Szöllösi úr aprobă acest mesaj.
--- Ion Durduroiu, Dialogurile Puterii

Primăvara lui 2003. În Rytan, războiul a devenit un obicei. Zachodiștii sunt într-o campanie de recapturare a anumitor teritorii momentan sub stăpânirea teroriștilor. În vederea stopării conflictului din orașul Sprengjuaras, sprijinul forțelor române a fost solicitat. Armata română a trimis în focul luptei cea mai bine pregătită unitate: "Cerbii roșii", în frunte cu generalul Oliver Kipeläinien. Sarcina lor era de a îngreuna desfășurarea acțiunilor teroriste până la venirea întăririlor zachodiste.

Ajunși la fața locului, Oliver Kipeläinien consultă harta orașului. Acesta era alcătuit din $N$ puncte strategice cheie și $M$ drumuri de legătură cu scopul de a facilita transportul armamentului. Din vina terenului nisipos, vehiculele blindate nu puteau traversa drumurile decât într-un singur sens, anume la vale. Astfel, generalul Oliver Kipeläinien a remarcat asemănarea teritoriului cu un graf orientat aciclic.

Scopul românilor era de a ține sub control teroriștii, reducându-le aria de influență, păstrând totuși aceleași posibilități de traversare a orașului. Planul era simplu: blocarea anumitor drumuri prin detonare și păstrarea altora, astfel încât, dacă inițial se putea ajunge din punctul strategic $X$ în punctul strategic $Y$, după eliminarea drumurilor, transportul de la $X$ la $Y$ să fie în continuare realizabil.

Fiecare drum avea un "cost" aferent, ce reprezenta cantitatea de combustibil necesar traversării lui. Uneori, un drum cu cost mai mic reducea semnificativ viteza de traversare, comparativ cu un drum mai costisitor. Cu toate acestea, Oliver Kipeläinien a prezentat a doua zi unității planul drumurilor lăsate în funcțiune, urmând ca pe celelalte să le blocheze. Ingeniozitatea sa s-a dovedit a fi de un real folos, înregistrând zero victime române. Zachodiștii au preluat cârma orașului. În țară, presa a lăudat actele de vitejie ale generalului și ale unității sale.

Astăzi, generalul Oliver Kipeläinien candidează la alegerile prezidențiale. Săpând în trecutul său, o echipă de jurnaliști descoperă adevărata față a evenimentelor de la Sprengjuaras. Cerând un punct de vedere al zachodiștilor în subordinea cărora se afla Oliver Kipeläinien, aceștia află ce plan adoptase de fapt generalul: Oliver Kipeläinien a ales exact drumurile de cost total minim pentru a reduce consumul de benzină la motor și pentru a diverti resursele la sistemul de sunet pentru a petrece cât mai mult timp la distracție în tanc, ferindu-se de conflict până la sosirea ajutoarelor. Imaginea generalului este pătată, iar acesta pierde alegerile în fața inamicului său politic, Pătrățel.

Cerință

Tu faci parte din echipa jurnaliștilor. Află ce drumuri a ales de fapt Oliver Kipeläinien și care este costul minim total de combustibil.

Date de intrare

Pe prima linie de la linia de intrare se vor afla două numere, $N$ și $M$. Urmează $M$ linii, fiecare descriind câte un drum prin $x_i$, $y_i$ și $c_i$, reprezentând un drum din punctul $x_i$ la $y_i$ al cărui cost este $c_i$.

Date de ieșire

Se va afișa un singur număr, anume costul minim posibil al drumurilor unui plan care păstrează relațiile de accesibilitate hărții inițiale.

Restricții și precizări

• $1 \le N \le M \le 50 \ 000$;
• $1 \le x_i, y_i \le N$;
• $1 \le c_i \le 10^6$.

Exemplu

stdin

7 11
1 2 7
2 7 11
1 6 5
6 2 5
1 3 9
3 6 3
3 7 2
6 4 7
4 7 10
2 5 3
5 7 6

stdout

43

Explicație

Drumurile alese de Oliver Kipeläinien sunt cele cu indexurile $4$, $5$, $6$, $8$, $9$, $10$ și $11$.