7. Krášlenie cestičiek

V Adamovej záhradke sa má konať veľká záhradnícka slávnosť, na ktorú prídu záhradníci zo široka-ďaleka. Chce, aby na túto slávnosť jeho záhradka vyzerala čo najlepšie. Už sa postaral o všetky svoje záhony, ale nepáčia sa mu cestičky, ktoré medzi nimi vedú.

Rozhodol sa, že teda záhradníkom dovolí, chodiť iba po niektorých cestičkách. Vyberie také, aby boli čo najmenej škaredé; ostatné kľudne škaredé byť môžu, lebo ich nikto neuvidí. Po vybraných cestičkách sa musí dať dostať od ľubovoľného záhonu k ľubovoľnému inému. Okrem toho mu ešte zostali nejaké peniaze, ktoré môže využiť na skrášlenie cestičiek. Skrášliť každú cestičku stojí rôzne veľa peňazí.

Pomôžte Adamovi vybrať, ktoré cestičky má nechať prístupné a určiť, ktoré ako skrášliť.

Úloha

Adamovu záhradku tvorí \(n\) záhonov, pospájaných \(m\) obojsmernými cestičkami.

Každá cestička má nejakú škaredosť \(w_i\) a cenu, za ktorú môže znížiť jej škaredosť o \(1\), \(c_i\). Adam má k dispozícii \(S\) peňazí, ktoré môže minúť na skrášľovanie cestičiek.

Vašou úlohou je vybrať \(n-1\) takých cestičiek, aby súčet ich škaredostí po skrášlení bol čo najmenší a aby sa po nich dalo dostať od každého záhonu ku každému. Je zaručené, že po pôvodných cestičkách sa dá dostať od každého ku každému. Skrášliť môžete každú cestičku ľubovoľne veľa krát, pričom za každé skrášlenie cestičky \(i\) zaplatíte \(c_i\) peňazí. Najviac môžete minúť \(S\) peňazí. Je povolené, aby škaredosť cestičky dosiahla 0 alebo aj záporné číslo.

Formát vstupu

Prvý riadok obsahuje dve kladné celé čísla \(n\) a \(m\) oddelené medzerou, označujúce počet záhonov a počet cestičiek. Záhony číslujeme od \(0\) do \(n-1\) a cestičky od \(0\) do \(m-1\).

Nasleduje \(m\) riadkov popisujúcich cestičky. Riadok \(i+1\) obsahuje v tomto poradí štyri čísla \(a_i\), \(b_i\), \(c_i\), \(w_i\) (\(0 \leq a_i, b_i < n\), \(a_i \neq b_i\), \(1 \leq c_i, w_i \leq 10^9\)). To značí, že cestička \(i\), so škaredosťou \(w_i\) a cenou skrášlenia \(c_i\), spája záhony \(a_i\) a \(b_i\). Medzi dvoma záhonmi môže ísť viacero cestičiek.

Posledný riadok obsahuje číslo \(S\) (\(0 \leq S \leq 10^9\)), počet Adamových peňazí.

Formát výstupu

Na prvom riadku vypíšte číslo \(K\) – súčet škaredostí vybraných ciest po skrášlení.

Potom vypíšte \(n-1\) riadkov. V každom riadku vypíšte dve čísla \(x\), \(v_x\), ktoré označujú, že cesta \(x\) je medzi vybranými a po skrášlení má škaredosť \(v_x\).

Cestičky môžete vypísať v ľubovoľnom poradí. Ak je riešení viacero, vypíšte ľubovoľné z nich.

Obmedzenia

Sú \(4\) sady vstupov po \(2\) body. Platia v nich nasledovné dodatočné obmedzenia:

Príklad

Input:

6 9
1 2 4 1
1 3 1 3
2 3 4 1
2 4 2 1
2 5 2 3
3 5 5 1
3 0 3 2
4 5 1 2
5 0 6 2
7

Output:

0
0 1
2 1
5 1
6 2
7 -5

Input:

3 3
2 1 7 9
0 1 7 5
0 2 2 1
2

Output:

5
2 0
1 5