Problem hidden
|This problem was hidden by Editorial Board member probably because it has incorrect language|version or invalid test data, or description of the problem is not clear.|

FLOW2509 - Luồng cực đại trên mạng - Max Flow

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


Được gửi lên bởi:special_one
Ngày:2009-01-04
Thời gian chạy:1s
Giới hạn mã nguồn:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Ngôn ngữ cho phép:C CSHARP CPP JAVA PAS-FPC

© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.