Cấp nước ký túc xá

Ký túc xá có $n$ ngôi nhà được đánh số từ $1$ đến $n$. Giữa các nhà có $p$ đường ống nước ngầm. Mỗi đường ống có một chiều cố định (nước chỉ chảy theo chiều đó) và một đường kính đặc trưng cho lượng nước tối đa mà ống chịu được.

Với mỗi ngôi nhà, có nhiều nhất một đường ống đi vào và nhiều nhất một đường ống đi ra.

Ta cần lắp bồn chứa và vòi nước như sau:

• Nhà nào có ống đi ra nhưng không có ống đi vào thì lắp một bồn chứa.
• Nhà nào có ống đi vào nhưng không có ống đi ra thì lắp một vòi nước.

Nước từ mỗi bồn chứa chảy theo dãy đường ống và đổ ra đúng một vòi nước. Để đường ống không bị vỡ, lượng nước chảy từ một bồn tới vòi tương ứng không được vượt quá đường kính của bất kỳ đường ống nào trên đường đi giữa chúng.

Hãy tìm lượng nước lớn nhất có thể dẫn an toàn từ mỗi bồn chứa tới vòi nước tương ứng.

Dữ liệu vào

• Dòng đầu chứa hai số nguyên $n$ và $p$: số ngôi nhà và số đường ống.
• $p$ dòng tiếp theo, mỗi dòng chứa ba số nguyên $a_i$, $b_i$, $d_i$: một đường ống đường kính $d_i$ đi từ nhà $a_i$ tới nhà $b_i$.

Dữ liệu ra

• Dòng đầu in số nguyên $t$: số cặp (bồn chứa, vòi nước).
• $t$ dòng tiếp theo, mỗi dòng in ba số nguyên $tan{k}_i$, $ta{p}_i$, $d_i$: chỉ số nhà đặt bồn chứa, chỉ số nhà đặt vòi nước, và lượng nước lớn nhất dẫn được.

Các dòng phải được in theo thứ tự tăng dần của $tan{k}_i$.

Ràng buộc

• $1\le n\le 1000$
• $0\le p\le n$
• $1\le a_i,b_i\le n$, $a_i\ne b_i$
• $1\le d_i\le {10}^6$
• Mỗi nhà có nhiều nhất một ống đi vào và nhiều nhất một ống đi ra.

Ví dụ