Centre for Gifted Education - Hanoi university of Technology

Cho một mạng G = (V, E) là đồ thị có hướng với n điểm và m cung, 1 là điểm phát và n là điểm thu. Từ 1 chỉ có cung đi ra và từ n chỉ có cung đi vào. Mỗi cung (u, v) của mạng được gán một số nguyên dương c(u, v) là khả năng thông qua của cung đó.

Một luồng cực đại trên mạng là một cách gán cho mỗi cung (u, v) một số nguyên f(u, v) thoả mãn:

Hãy tìm luồng cực đại trên mạng G

Input

Dòng 1: Chứa số đỉnh n và số cung m của đồ thị G (2 <= n <= 100)

M dòng tiếp theo, mỗi dòng chứa ba số u, v, c(u, v) thể hiện cho một cung (u, v) và khả năng thông qua của cung đó là c(u, v)

Output

Dòng 1: Ghi giá trị luồng tìm được

Các dòng tiếp theo, mỗi dòng chứa ba số x, y, f(x, y) thể hiện (x, y) là một cung và luồng gán cho cung (x, y) là f(x, y) (Những cung nào không có luồng (f(x, y) = 0) không cần phải ghi vào Output file).

Example

Input:
6 8
1 2 5
1 3 5
2 4 6
2 5 3
3 4 3
3 5 1
4 6 6
5 6 6

Output:
9
1 2 5
1 3 4
2 4 3 
2 5 2
3 4 3
3 5 1
4 6 6
5 6 3