Primăvara lui '03

Time limit: 1s Memory limit: 512MB Input: Output:

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.

Marea Teroare\text{Marea Teroare}

Ajunși la fața locului, Oliver Kipeläinien consultă harta orașului. Acesta era alcătuit din NN puncte strategice cheie și MM 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 XX în punctul strategic YY, după eliminarea drumurilor, transportul de la XX la YY 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.

și Operațiunea Polonezilor\text{și Operațiunea Polonezilor}

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, NN și MM. Urmează MM linii, fiecare descriind câte un drum prin xix_i, yiy_i și cic_i, reprezentând un drum din punctul xix_i la yiy_i al cărui cost este cic_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

  • 1NM50 0001 \le N \le M \le 50 \ 000;
  • 1xi,yiN1 \le x_i, y_i \le N;
  • 1ci1061 \le c_i \le 10^6.
# Punctaj Restricții
1 8 M19M \le 19
2 12 Există un lanț de lungime NN
3 12 M80M \le 80
4 18 M500M \le 500
5 20 M5 000M \le 5 \ 000
6 30 Fără restricții suplimentare

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 44, 55, 66, 88, 99, 1010 și 1111.

Log in or sign up to be able to send submissions!