29831번 - Kulude jagamine 스페셜 저지다국어

$N$ sõpra käisid Informaatika Maailmameistrivõistlustel. Võistlusel osalemine tekitas neile erinevaid ühiseid kulutusi, kusjuures iga kulu eest maksis üks sõpradest.

Pärast võistlust soovivad sõbrad kulud võrdselt ära jagada. Leida minimaalse kogusummaga pangaülekannete komplekt, mille abil seda teha.

Sisendi esimesel real on sõprade arv $N$ ($1 \le N \le 50\,000$) ja tehtud kulutuste arv $M$ ($0 \le M \le 50\,000$). Tähistame sõpru arvudega $1, \ldots, N$.

Järgmisel $M$ real on tehtud kulutuste andmed. Igal real on täisarvud $X$ ja $S$, kus $X$ ($1 \le X \le N$) on selle selle sõbra number, kes maksis, ja $S$ ($S > 0$) on makstud summa. Võib eeldada, et kõik makstud summad jaguvad täpselt sõprade arvuga ja et kõigi kulude kogusumma ei ületa $1\,000\,000\,000$.

Esimesele reale väljastada lahenduseks olevate pangaülekannete kogusumma $K$.

Teisele reale väljastada ülekannete arv $P$. Järgmisele $P$ reale väljastada igaühele kolm tühikutega eraldatud täisarvu $X$, $Y$ ja $S$ ($1 \le X \le N$, $1 \le Y \le N$, $X \ne Y$, $S > 0$), mis näitavad, et sõber $X$ kannab sõbrale $Y$ üle summa $S$.

Kõigi ülekannete kogusumma peab olema vähim võimalik. Kui sobivaid ülekannete komplekte on mitu, väljastada ükskõik milline neist.