Problem
En se rend dans sa forêt de champignons pour cueillir des champignons.
Il y a m chemins orientés dans la forêt des champignons reliant n arbres. Les champignons poussent sur tous les chemins. Quand En marche le long d'un chemin, il ramasse tous les champignons sur ce chemin. Cependant, la forêt des champignons a un sol si fertile que les champignons poussent à un rythme fantastique. De nouveaux champignons poussent dès que En finit de cueillir des champignons sur le chemin. A savoir, après qu'En passe le long du chemin pour la ième fois, pousse i moins de champignons qu'avant ce passage. Ainsi, si le chemin avait initialement x champignons, alors En récoltera x champignons au premier passage, x - 1 champignon au second, x - 1 - 2 champignons au troisième, et ainsi sur. Cependant, le nombre de champignons ne peut pas devenir inférieur à 0.
Par exemple, laissez initialement 9 champignons pousser sur le chemin. Ensuite, le nombre de champignons que En collectera est de 9, 8, 6 et 3 pour les passes un à quatre. A partir du cinquième passage, En ne pourra plus rien récolter sur ce chemin (mais pourra toujours marcher dessus).
Fr a décidé de partir de l'arbre s. Quel est le nombre maximum de champignons qu'il peut récolter en se déplaçant uniquement le long des chemins décrits ?
Saisie :
La première ligne contient deux entiers n et m (1 ≤ n ≤ 300000, 0 ≤ m ≤ 300000) — respectivement le nombre d'arbres et le nombre de chemins orientés dans la Forêt Champignon.
Chacune des m lignes suivantes contient trois entiers x, y et w (1 ≤ x, y ≤ n, 0 ≤ w ≤ 10
8 ) décrivant un chemin qui mène de l'arbre x à l'arbre y avec w champignons initialement. Il existe des chemins qui mènent d'un arbre au même arbre, ainsi que plusieurs chemins reliant la même paire d'arbres.
La dernière ligne contient un seul entier s (1 ≤ s ≤ n) — Position de départ de En.
Sortie :
Imprimer un seul entier — Le nombre maximum de champignons qu'En peut ramasser sur son chemin.
Exemples :
| Entrée |
Sortie |
2 2
1 2 4
2 1 4
1 |
16 |
3 3
1 2 4
2 3 3
1 3 8
1 |
8 |
Explications :
Dans le premier exemple, En peut faire trois fois le tour du cercle et récolter 4 + 4 + 3 + 3 + 1 + 1 = 16 champignons. Après cela, En n'aura plus de champignons à ramasser.
Dans le deuxième exemple, En peut aller à l'arbre 3 et cueillir 8 champignons sur le chemin de l'arbre 1 à l'arbre 3.