Problem
En va nella sua foresta di funghi per raccogliere funghi.
Ci sono m sentieri orientati nella Foresta dei Funghi che collegano n alberi. I funghi crescono su ogni sentiero. Quando En cammina lungo un sentiero, raccoglie tutti i funghi su quel sentiero. Tuttavia, la foresta dei funghi ha un terreno così fertile che i funghi crescono a un ritmo fantastico. Nuovi funghi crescono non appena En finisce di raccogliere funghi sul sentiero. Vale a dire, dopo che En passa lungo il sentiero per l'i-esima volta, cresce i meno funghi di quanto non fosse prima di questo passaggio. Quindi, se il percorso inizialmente aveva x funghi, allora En raccoglierà x funghi nel primo passaggio, x - 1 fungo nel secondo, x - 1 - 2 funghi nel terzo, e così SU. Tuttavia, il numero di funghi non può essere inferiore a 0.
Ad esempio, lascia che inizialmente crescano 9 funghi sul sentiero. Quindi il numero di funghi che En raccoglierà è 9, 8, 6 e 3 per i passaggi da uno a quattro. Dal quinto passaggio in poi, En non sarà in grado di raccogliere nulla da questo percorso (ma potrà comunque percorrerlo).
En ha deciso di partire dall'albero s. Qual è il numero massimo di funghi che può raccogliere muovendosi solo lungo i percorsi descritti?
Inserimento:
La prima riga contiene due numeri interi n e m (1 ≤ n ≤ 300000, 0 ≤ m ≤ 300000) — rispettivamente il numero di alberi e il numero di sentieri orientati nella Foresta dei Funghi.
Ognuna delle m righe successive contiene tre numeri interi x, y e w (1 ≤ x, y ≤ n, 0 ≤ w ≤ 10
8 ) che descrive un percorso che porta dall'albero x all'albero y inizialmente con w funghi. Esistono percorsi che conducono da un albero allo stesso albero, così come diversi percorsi che collegano la stessa coppia di alberi.
L'ultima riga contiene un singolo numero intero s (1 ≤ s ≤ n) — Posizione di partenza di En.
Uscita:
Stampa un singolo numero intero — Il numero massimo di funghi che En può raccogliere lungo il suo cammino.
Esempi:
| Input |
Uscita |
2 2
1 2 4
2 1 4
1 |
16 |
3 3
1 2 4
2 3 3
1 3 8
1 |
8 |
Spiegazioni:
Nel primo esempio, En può fare il giro del cerchio tre volte e raccogliere 4 + 4 + 3 + 3 + 1 + 1 = 16 funghi. Dopodiché, non ci saranno più funghi da raccogliere per En.
Nel secondo esempio En può andare all'albero 3 e raccogliere 8 funghi lungo il percorso dall'albero 1 all'albero 3.