Problem
En va a su bosque de hongos para recolectar hongos.
Hay m caminos orientados en el Bosque de Hongos que conectan n árboles. Los hongos crecen en todos los caminos. Cuando En camina por un camino, recoge todos los hongos en ese camino. Sin embargo, el Bosque de Hongos tiene un suelo tan fértil que los hongos crecen a un ritmo fantástico. Nuevos hongos crecen tan pronto como En termina de recoger hongos en el camino. Es decir, después de que En pasa por el camino por i-ésima vez, crecen menos hongos que antes de este pasaje. Por lo tanto, si el camino inicialmente tenía x hongos, entonces En recolectará x hongos en la primera pasada, x - 1 hongo en el segundo, x - 1 - 2 hongos en el tercero, y así en. Sin embargo, el número de hongos no puede ser inferior a 0.
Por ejemplo, deje crecer inicialmente 9 hongos en el camino. Luego, el número de hongos que recolectará En es 9, 8, 6 y 3 para las pasadas uno a cuatro. A partir del quinto paso, En no podrá recolectar nada de este camino (pero aún podrá caminar por él).
En decidió empezar desde el árbol s. ¿Cuál es el número máximo de hongos que puede recolectar moviéndose solo por los caminos descritos?
Entrada:
La primera línea contiene dos enteros n y m (1 ≤ n ≤ 300000, 0 ≤ m ≤ 300000) — el número de árboles y el número de caminos orientados en el Bosque de Champiñones, respectivamente.
Cada una de las siguientes m líneas contiene tres números enteros x, y y w (1 ≤ x, y ≤ n, 0 ≤ w ≤ 10
8 ) que describe un camino que conduce del árbol x al árbol y con w hongos inicialmente. Hay caminos que llevan de un árbol al mismo árbol, así como varios caminos que conectan el mismo par de árboles.
La última línea contiene un único número entero s (1 ≤ s ≤ n) — Posición inicial de En.
Salida:
Imprime un solo entero — El número máximo de hongos que En puede recolectar en su camino.
Ejemplos:
| Entrada |
Salida |
2 2
1 2 4
2 1 4
1 |
16 |
3 3
1 2 4
2 3 3
1 3 8
1 |
8 |
Explicaciones:
En el primer ejemplo, En puede dar tres vueltas al círculo y recolectar 4 + 4 + 3 + 3 + 1 + 1 = 16 hongos. Después de eso, En no habrá hongos para recolectar.
En el segundo ejemplo, En puede ir al árbol 3 y recoger 8 hongos en el camino del árbol 1 al árbol 3.