Problem
Một đồ thị có hướng có trọng số được đưa ra. Cần phải xác định xem nó có chứa chu trình có trọng số âm hay không. Đảm bảo rằng tất cả các đỉnh của đồ thị đều có thể truy cập được từ đỉnh đầu tiên.
Đầu vào:
Dòng đầu tiên của tệp đầu vào chứa hai số tự nhiên n và m — lần lượt là số đỉnh và số cạnh của đồ thị ( n ≤ 1 111, m ≤ 11 111).
m dòng tiếp theo chứa mô tả các cạnh, mỗi dòng một cạnh. Số cạnh i được mô tả bằng ba số bi, ei và wi — số đầu của xương sườn và trọng lượng của nó, tương ứng (1 ≤ bi, ei ≤ n, −100 000 ≤ wi ≤ 100 000) . Lưu ý rằng biểu đồ có thể có nhiều cạnh và nhiều vòng.
Đầu ra:
Dòng đầu tiên của tệp đầu ra phải chứa có nếu biểu đồ chứa chu trình có trọng số âm và không — nếu không.
Ví dụ
<đầu>
| # |
Đầu vào |
Đầu ra |
| 1 |
4 4
2 1-4
1 2 1
3 4 2
2 3 3
| có |
| 2 |
4 6
2 1 4
1 2 1
3 4 2
2 3 3
1 1 2
1 2 2
| không |