Problem
En đến Rừng nấm của cô ấy để hái nấm.
Có m con đường định hướng trong Rừng Nấm kết nối n cây. Nấm mọc trên mọi lối đi. Khi Én đi trên một con đường, Én hái tất cả những cây nấm trên con đường đó. Tuy nhiên, Rừng Nấm có đất đai màu mỡ nên nấm phát triển với tốc độ chóng mặt. Nấm mới mọc ngay sau khi Én hái xong nấm trên đường đi. Cụ thể là, sau khi En đi dọc theo con đường lần thứ i, số lượng nấm mọc ra của tôi ít hơn so với trước khi đi qua con đường này. Do đó, nếu đường dẫn ban đầu có x nấm, thì En sẽ thu thập x nấm ở lượt đầu tiên, x - 1 nấm ở lượt thứ hai, x - 1 - 2 nấm ở lượt thứ ba, v.v. TRÊN. Tuy nhiên, số lượng nấm không được nhỏ hơn 0.
Ví dụ, ban đầu hãy để 9 cây nấm mọc trên đường đi. Sau đó, số nấm mà En sẽ thu thập là 9, 8, 6 và 3 cho các lượt từ một đến bốn. Từ lượt thứ năm trở đi, En sẽ không thể thu thập bất cứ thứ gì từ con đường này (nhưng vẫn có thể đi bộ trên đó).
En quyết định bắt đầu từ cây s. Số lượng nấm tối đa anh ta có thể thu thập bằng cách chỉ di chuyển dọc theo các con đường được mô tả là bao nhiêu?
Đầu vào:
Dòng đầu tiên chứa hai số nguyên n và m (1 ≤ n ≤ 300000, 0 ≤ m ≤ 300000) — lần lượt là số cây và số đường định hướng trong Rừng Nấm.
Mỗi m dòng tiếp theo chứa ba số nguyên x, y và w (1 ≤ x, y ≤ n, 0 ≤ w ≤ 10
8 ) mô tả đường dẫn từ cây x đến cây y với w nấm ban đầu. Có những con đường dẫn từ một cây đến cùng một cây, cũng như một số con đường nối cùng một cặp cây.
Dòng cuối cùng chứa một số nguyên s (1 ≤ s ≤ n) — Vị trí xuất phát của En.
Đầu ra:
In một số nguyên duy nhất — Số lượng nấm tối đa mà En có thể thu thập trên đường đi của mình.
Ví dụ:
| Đầu vào |
Đầu ra |
2 2
1 2 4
2 1 4
1 |
16 |
3 3
1 2 4
2 3 3
1 3 8
1 |
8 |
Giải thích:
Trong ví dụ đầu tiên, En có thể đi vòng tròn ba lần và thu thập 4 + 4 + 3 + 3 + 1 + 1 = 16 cái nấm. Sau đó sẽ không còn nấm để Én thu thập.
Trong ví dụ thứ hai En có thể đến cây 3 và hái 8 cây nấm trên đường đi từ cây 1 đến cây 3.