Problem
En, mantar toplamak için Mantar Ormanına gider.
Mantar Ormanı'nda n ağacı birbirine bağlayan m yönelimli yollar vardır. Mantarlar her yolda büyür. En bir yol boyunca yürüdüğünde, o yoldaki tüm mantarları toplar. Ancak Mantar Ormanı o kadar verimli bir toprağa sahiptir ki, mantarlar inanılmaz bir hızla büyür. En, yoldaki mantarları toplamayı bitirir bitirmez yeni mantarlar büyür. Yani En, i. kez yol boyunca geçtikten sonra, bu geçiş öncesine göre i daha az mantar üretir. Böylece, yolun başlangıçta x mantarı varsa, En ilk geçişte x mantar, ikinci geçişte x - 1 mantar, üçüncü geçişte x - 1 - 2 mantar toplayacaktır ve böylece Açık. Ancak mantar sayısı 0'dan az olamaz.
Örneğin, başlangıçta yolda 9 mantar büyümesine izin verin. Daha sonra En'in toplayacağı mantar sayısı 9, 8, 6 ve birden dörde geçişler için 3'tür. Beşinci geçişten itibaren En, bu yoldan hiçbir şey toplayamayacak (ancak yine de üzerinde yürüyebilecek).
En, ağaçlardan başlamaya karar verdi. Yalnızca açıklanan yollar boyunca ilerleyerek toplayabileceği maksimum mantar sayısı nedir?
Giriş:
İlk satır iki tamsayı içerir n ve m (1 ≤ n ≤ 300000, 0 ≤ m ≤ 300000) — sırasıyla Mantar Ormanı'ndaki ağaç sayısı ve yönlendirilmiş yol sayısı.
Sonraki m satırın her biri üç tam sayı x, y ve w içerir (1 ≤ x, y ≤ n, 0 ≤ w ≤ 10
8) ), başlangıçta w mantarlı x ağacından y ağacına giden bir yolu tarif ediyor. Bir ağaçtan aynı ağaca giden yollar olduğu gibi, aynı ağaç çiftini birbirine bağlayan birçok yol vardır.
Son satır tek bir tamsayı içerir s (1 ≤ s ≤ n) — En'in başlangıç pozisyonu.
Çıktı:
Tek bir tamsayı yazdır — En'in yolda toplayabileceği maksimum mantar sayısı.
Örnekler:
| Giriş |
Çıktı |
2 2
1 2 4
2 1 4
1 |
16 |
3 3
1 2 4
2 3 3
1 3 8
1 |
8 |
Açıklamalar:
İlk örnekte En, çemberin etrafında üç kez dönerek 4 + 4 + 3 + 3 + 1 1+ 1 = 16 mantar toplayabilir. Bundan sonra En'in toplayacağı mantar kalmayacak.
İkinci örnekte En, 3. ağaca gidebilir ve 1. ağaçtan 3. ağaca giden yolda 8 mantar toplayabilir.