Î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ţă 10 RON, iar Ghiţă lui Daniel tot 10 RON, este de ajuns ca Gigel să dea 10 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 N M, reprezentând numărul prieteni din grup, respectiv numărul de împrumuturi făcute. Prietenii sunt numerotaţi de la 1 la N. Următoarele M linii vor conţine câte trei numere naturale separate prin spaţiu A B C cu semnificaţia: ″A trebuie să plătească C RON lui B″.
Date de ieşire
Fişierul de ieşire datorii.out va conţine pe prima linie două numere naturale separate prin spaţiu K S, unde K reprezintă numărul minim de tranzacţii efectuate, iar S suma totală minimă pentru K tranzacţii. Pe următoarele K linii se vor scrie câte trei numere naturale separate prin spaţiu X Y Z cu semnificaţia: X plăteşte Z RON lui Y.
Restricţii
2 ≤ N ≤ 20
1 ≤ M ≤ 100
1 ≤ C ≤ 100
Exemple
datorii.in
datorii.out
Explicaţii
6 5
1 2 10
2 3 10
4 5 5
5 6 5
6 4 5
1 10
1 3 10
S-a efectuat o singură tranzacţie: persoana 1 a dat 10 RON persoanei 3. Suma minimă tranzacţionată este 10 RON.