• محدودیت زمان: ۱ ثانیه
• محدودیت حافظه: ۲۵۶ مگابایت

در شهر شکرستان $n$ بانک وجود دارد. هر روز تعدادی تراکنش مالی میان بانک‌ها باید اتفاق بیافتد. گلابی که رئیس بانک مرکزی شکرستان است متوجه شده که مجموع تراکنش‌های بین بانک‌ها امکان دارد خیلی زیاد باشد برای همین دنبال کم کردن مجموع مبلغ آن‌ها است.

او تراکنش‌های مالی میان بانک‌ها در هر روز را می‌بیند و سعی می‌کند با کمترین مجموع مبلغ تراکنش، تراکنش مالی میان بانک‌ها را انجام بدهد.

به او کمک کنید که این کار را انجام دهد طوری که شرایط بالا رعایت شود. توجه کنید نیازی نیست تعداد تراکنش‌ها کمینه شود بلکه باید مجموع مبلغ کل تراکنش‌ها کمینه باشد.

ورودی

در خط اول به ترتیب دو عدد $n$ و $m$ ورودی داده می‌شود که $n$ تعداد بانک‌های شهر شکرستان است و $m$ تعداد تراکنش‌های مالی میان بانک‌ها در آن روز است.

$$1 \leq n \leq 1000$$ $$0 \le m \le 10^5$$

در $m$ خط بعد در هر خط به ترتیب سه عدد $u$ و $v$ و $w$ داده می‌شود که نشان دهنده‌ی این است که در این تراکنش $w$ همت (هزار میلیارد تومان) از بانک $u$ به بانک $v$ باید انتقال داده شود.

$$1 \leq u, v \leq n, \quad u \neq v$$ $$1 \le w \le 10^9$$

خروجی

در خط اول ورودی عدد $k$ که تعداد تراکنش برای انجام تراکنش‌های مالی میان بانک‌ها است را خروجی دهید.

$$0 \leq k \leq 10^5$$

سپس در هرکدام از $k$ خط بعدی به ترتیب سه عدد $u$ و $v$ و $w$ را خروجی دهید. که نشان‌ دهنده‌ی این هستند که در این تراکنش $w$ همت (هزار میلیارد تومان) از بانک $u$ به بانک $v$ انتقال داده می‌شود.

$$1 \leq u, v \leq n, \quad u \neq v$$ $$1 \leq w \leq 10^{14}$$

اگر چند روش برای انجام تراکنش‌ها وجود دارد، یکی را به دلخواه چاپ کنید.

مثال‌ها

ورودی نمونه ۱

5 7
1 2 10
1 3 4
2 3 9
3 2 8
3 5 9
4 3 2
2 5 4

خروجی نمونه ۱

4
1 2 5
1 5 9
3 5 2
4 5 2

ورودی نمونه ۲

3 3
1 2 10
2 3 10
3 1 10

خروجی نمونه ۲

0

ورودی نمونه ۳

3 2
1 2 10
2 3 7

خروجی نمونه ۳

2
1 2 3
1 3 7