Într-un grup de prieteni nu este un lucru ieşit din comun, ca unii să primească bani împrumut de la alţii. Datoriile ce se formează astfel sunt rezolvate ulterior. De exemplu, dacă Gigel îi plăteşte o bere lui Ghiţă, data viitoare va plăti Ghiţă berea pentru amândoi şi datoriile vor fi rezolvate.
Dacă după un timp mai îndelungat împrumuturile nu se rezolvă de la sine, grupul de prieteni se adună pentru a rezolva problemele financiare. La o asemenea întâlnire este de dorit, ca numărul de tranzacţii efectuate să fie minim. De exemplu, dacă Gigel îi datorează lui Ghiţă RON, iar Ghiţă lui Daniel tot RON, este de ajuns ca Gigel să dea RON lui Daniel şi toate datoriile vor fi rezolvate.
Cerinţă
Cunoscând toate împrumuturile ce au fost făcute în grupul de prieteni, determinaţi o modalitate de rezolvare a datoriilor cu număr minim de tranzacţii. Dacă există mai multe posibilităţi cu număr minim de tranzacţii, determinaţi o modalitate pentru care suma totală de bani tranzacţionată să fie minimă. Dacă există mai multe posibilităţi cu număr minim de tranzacţii şi sumă totală de bani minimă, afişaţi oricare dintre acestea.
Date de intrare
Fişierul de intrare datorii.in va conţine pe prima linie două numere naturale separate prin spaţiu , reprezentând numărul prieteni din grup, respectiv numărul de împrumuturi făcute. Prietenii sunt numerotaţi de la la . Următoarele linii vor conţine câte trei numere naturale separate prin spaţiu cu semnificaţia: " trebuie să plătească RON lui ".
Date de ieșire
Fişierul de ieşire datorii.out va conţine pe prima linie două numere naturale separate prin spaţiu , unde reprezintă numărul minim de tranzacţii efectuate, iar suma totală minimă pentru tranzacţii. Pe următoarele linii se vor scrie câte trei numere naturale separate prin spaţiu cu semnificaţia: plăteşte RON lui .
Restricții și precizări
Exemplu
datorii.in
6 5
1 2 10
2 3 10
4 5 5
5 6 5
6 4 5
datorii.out
1 10
1 3 10
Explicație
S-a efectuat o singură tranzacţie: persoana a dat RON persoanei . Suma minimă tranzacţionată este RON.