Problem
En pergi ke Hutan Cendawannya untuk mengumpul cendawan.
Terdapat laluan berorientasikan m di Hutan Cendawan yang menghubungkan n pokok. Cendawan tumbuh di setiap laluan. Apabila En berjalan di sepanjang laluan, dia memungut semua cendawan di laluan itu. Walau bagaimanapun, Hutan Cendawan mempunyai tanah yang subur sehingga cendawan tumbuh pada kadar yang hebat. Cendawan baru tumbuh sebaik sahaja En selesai memetik cendawan di laluan. Iaitu, selepas En melalui laluan untuk kali ke-i, tumbuh i cendawan lebih sedikit daripada sebelum petikan ini. Oleh itu, jika laluan itu pada mulanya mempunyai x cendawan, maka En akan mengumpul x cendawan pada laluan pertama, x - 1 cendawan di kedua, x - 1 - 2 cendawan pada laluan ketiga, dan seterusnya pada. Walau bagaimanapun, bilangan cendawan tidak boleh kurang daripada 0.
Sebagai contoh, biarkan pada mulanya 9 cendawan tumbuh di laluan. Maka bilangan cendawan yang En akan kumpul ialah 9, 8, 6, dan 3 untuk pas satu hingga empat. Dari pas kelima dan seterusnya, En tidak akan dapat mengumpul apa-apa dari laluan ini (tetapi masih boleh berjalan di atasnya).
En memutuskan untuk bermula dari pokok s. Berapakah bilangan maksimum cendawan yang dia boleh kumpul dengan hanya bergerak di sepanjang laluan yang diterangkan?
Input:
Baris pertama mengandungi dua integer n dan m (1 ≤ n ≤ 300000, 0 ≤ m ≤ 300000) — bilangan pokok dan bilangan laluan berorientasikan di Hutan Cendawan, masing-masing.
Setiap baris m seterusnya mengandungi tiga integer x, y dan w (1 ≤ x, y ≤ n, 0 ≤ w ≤ 10
8 ) menerangkan laluan yang menghala dari pokok x ke pokok y dengan w cendawan pada mulanya. Terdapat laluan yang menuju dari pokok ke pokok yang sama, serta beberapa laluan yang menghubungkan sepasang pokok yang sama.
Baris terakhir mengandungi satu integer s (1 ≤ s ≤ n) — Kedudukan permulaan En.
Output:
Cetak satu integer — Bilangan maksimum cendawan yang En boleh kumpul dalam perjalanannya.
Contoh:
| Input |
Output |
2 2
1 2 4
2 1 4
1 |
16 |
3 3
1 2 4
2 3 3
1 3 8
1 |
8 |
Penjelasan:
Dalam contoh pertama, En boleh mengelilingi bulatan tiga kali dan mengumpul 4 + 4 + 3 + 3 + 1 + 1 = 16 cendawan. Selepas itu, tiada lagi cendawan untuk En kumpulkan.
Dalam contoh kedua En boleh pergi ke pokok 3 dan memetik 8 cendawan di laluan dari pokok 1 hingga pokok 3.