Problem
Anne geht in seinen Grib Forest, um Pilze zu sammeln.
Im Gribn-Wald verbinden m orientierte Wege n Bäume. Es gibt Pilze auf jeder Straße. Wenn Anne durch die Straße geht, sammelt er alle Pilze auf dieser Straße. Im Gribune-Wald wachsen jedoch solche fruchtbaren Böden, die Pilze mit fantastischen Geschwindigkeiten wachsen. Neue Pilze wachsen auf, sobald Anne die Pilze auf der Straße sammelt. Genau, nach En geht durch die i-time Straße, es wächst auf i Pilze weniger als zuvor. Also, wenn es Pilze auf der Straße auf der ersten Stelle, En wird x Pilze in der ersten Passage sammeln, x-1 Pilze in der zweiten, x - 1 - 2 Pilze in der dritten und so weiter. Die Zahl der Pilze kann jedoch nicht kleiner als 0 sein.
Lassen Sie beispielsweise 9 Pilze auf der Straße wachsen. Dann ist die Anzahl der Pilze, die An sammeln wird 9, 8, 6 und 3 für die Durchgänge von der ersten bis vierten. Beginnend auf dem fünften Gehweg, En kann nichts von dieser Straße bekommen (aber immer noch kann auf ihm gehen).
Eine Entscheidung, mit einem Baum zu beginnen. Was ist die maximale Anzahl von Pilzen, die er sammeln kann, sich nur auf den beschriebenen Straßen bewegen?
Eingabe:Die erste Linie enthält zwei ganze Zahlen n und m (1 < n < n < 300000, 0 < m < 300000) - Anzahl der Bäume und Anzahl der orientierten Pfade im Gribne-Wald.
Jede der folgenden m Zeilen enthält drei ganze Zahlen x, y und w (1 ≤ x, y ≤ n, 0 ≤ w ≤ 10
8)Beschreibung des Pfades, der von Holz x zu Baum y mit w Pilzen ursprünglich führt. Die Pfade, die vom Baum zum Baum führen, sind möglich, sowie mehrere Wege, die das gleiche Baumpaar verbinden.
Die letzte Zeile enthält eine ganze Zahl s (1 < s < n) - Ena ' s Ausgangsposition.
Ausgangsdaten:Nehmen Sie eine ganze Zahl, die maximale Anzahl von Pilzen, die En auf seinem Weg sammeln kann.
Beispiele:| Eingangsdaten | Ausgangsdaten |
2
1 2 4
Artikel 1
1 | ANHANG |
3
1 2 4
Artikel 3
1 3 8
1 | 8) |
Beschreibung:Im ersten Beispiel kann En drei Runden nehmen und 4 + 4 + 3 + 3 + 1 + 1 = 16 Pilze sammeln. Danach wird es keine Pilze geben En kann sammeln.
Im zweiten Beispiel kann En zum Baum 3 gehen und acht Pilze auf der Straße von Baum 1 zu Baum 3 sammeln.