Problem
En vai para sua Floresta de Cogumelos para coletar cogumelos.
Existem m caminhos orientados na Floresta de Cogumelos conectando n árvores. Cogumelos crescem em todos os caminhos. Quando En caminha por um caminho, ele colhe todos os cogumelos desse caminho. No entanto, a Floresta dos Cogumelos tem um solo tão fértil que os cogumelos crescem a um ritmo fantástico. Novos cogumelos crescem assim que En termina de colher cogumelos no caminho. Ou seja, depois que En passa pelo caminho pela i-ésima vez, cresce i menos cogumelos do que antes dessa passagem. Assim, se o caminho inicialmente tinha x cogumelos, En irá coletar x cogumelos na primeira passagem, x - 1 cogumelo na segunda, x - 1 - 2 cogumelos na terceira, e assim sobre. No entanto, o número de cogumelos não pode ser menor que 0.
Por exemplo, deixe inicialmente 9 cogumelos crescerem no caminho. Então, o número de cogumelos que En coletará é 9, 8, 6 e 3 para as passagens de um a quatro. A partir da quinta passagem, En não poderá coletar nada deste caminho (mas ainda poderá caminhar por ele).
En decidiu começar com as árvores. Qual é o número máximo de cogumelos que ele pode coletar movendo-se apenas pelos caminhos descritos?
Entrada:
A primeira linha contém dois inteiros n e m (1 ≤ n ≤ 300000, 0 ≤ m ≤ 300000) — o número de árvores e o número de caminhos orientados na Floresta de Cogumelos, respectivamente.
Cada uma das próximas m linhas contém três inteiros x, y e w (1 ≤ x, y ≤ n, 0 ≤ w ≤ 10
8 ) descrevendo um caminho que leva da árvore x à árvore y com inicialmente w cogumelos. Existem caminhos que levam de uma árvore à mesma árvore, assim como vários caminhos ligando o mesmo par de árvores.
A última linha contém um único inteiro s (1 ≤ s ≤ n) — Posição inicial de En.
Saída:
Imprima um único inteiro — O número máximo de cogumelos que En pode coletar em seu caminho.
Exemplos:
| Entrada |
Saída |
2 2
1 2 4
2 1 4
1 |
16 |
3 3
1 2 4
2 3 3
1 3 8
1 |
8 |
Explicações:
No primeiro exemplo, En pode dar três voltas no círculo e coletar 4 + 4 + 3 + 3 + 1 + 1 = 16 cogumelos. Depois disso, não haverá cogumelos para En coletar.
No segundo exemplo, En pode ir para a árvore 3 e colher 8 cogumelos no caminho da árvore 1 para a árvore 3.