Infomatrix




Două companii distribuie reviste într-un județ în care există un număr de n orașe și m șosele pe care se poate circula în ambele sensuri. Pentru fiecare șosea se cunoaște costul unui drum pe șoseaua respectivă. Fiecare companie dorește să pună la punct o rețea de distribuție care să-i permită să poată transporta reviste dintr-un oraș în oricare altul. Evident, fiecare companie va dori să obțină o rețea de distribuție al cărei cost total (suma costurilor șoselelor din rețea) să fie minim. Din nefericire, cele două companii rivale nu își pot permite să aibă rețele de distribuție identice. Ca urmare, ele vor alege rețele de distribuție puțin diferite. Va trebui să determinați diferența dintre costurile totale ale celor două rețele de distribuție știind că aceste două costuri sunt cele mai mici posibile și că rețelele nu pot fi complet identice.

Prima linie a fișierului de intrare RIVALS.IN conține numărul n al orașelor și numărul m al șoselelor. Fiecare dintre următoarele m linii conține trei numere întregi x, y și c cu semnificația: există o șosea între orașele x și y, al cărei cost este c. Numerele de pe o linie vor fi separate prin spații.

Fișierul de ieșire RIVALS.OUT trebuie să conțină o singură linie pe care se va afla diferența dintre costurile totale ale celor două rețele de distribuție.

  • 2 ≤ n ≤ 500;
  • 1 ≤ m ≤ 5000;
  • orașele sunt identificate prin numere cuprinse între 1 și n;
  • există posibilitatea ca diferența să fie 0 dacă cele două rețele de distribuție sunt diferite, dar au același cost total;
  • costurile șoselelor sunt numere întregi cuprinse între 1 și 1000.


  • RIVALS.IN
    4 5
    1 2 3
    1 3 5
    2 3 3
    2 4 5
    3 4 1

    RIVALS.OUT
    2