Заморожені бутони троянд#6619
Зима наближається, і всі експерти попереджають, що вона буде найхолоднішою за останні сто років. Фредді потрібно подбати про те, щоб його сад не постраждав. Одне з найважливіших завдань — стежити за тим, щоб у його великій системі поливу не залишалося води.
Вся вода надходить із центрального вузла і по трубах розподіляється до сусідніх вузлів і так далі. Кожен вузол є або розбризкувачем (бутоном троянди) без вихідної труби, або внутрішнім вузлом з однією або кількома вихідними трубами, що ведуть до інших вузлів. У кожному вузлі є рівно одна вхідна труба, за винятком центрального вузла, який забирає воду безпосередньо з колодязя і не має вхідної труби. У кожній трубі є клапан, який зупиняє всю воду, що проходить через трубу. Клапани різної якості та віку, тому деякі з них може бути важче закрити, ніж інші.
Фредді добре знає свої клапани і присвоїв кожній трубі значення, що позначає кількість зусиль, необхідних для закриття відповідного клапана. Він просить вас допомогти йому підрахувати мінімальне зусилля, необхідне для закриття деяких клапанів, щоб вода не надходила в розбризкувачі.
Складається з кількох тестів. Кожен тест починається з рядка з двома цілими числами: кількістю вузлів n~(2 \le n \le 1000) і номером центрального вузла c~(1 \le c \le n). Кожен з наступних n - 1 рядків представляє один канал і містить три цілі числа u, v~(1 \le u, v \le n) і w~(1 \le w \le 1000), де і — вузли, з'єднані трубою, а — зусилля, необхідне для закриття клапана на цій трубі. Ви можете припустити, що кожен вузол доступний з центрального вузла.
Для кожного тесту виведіть в одному рядку мінімальну суму зусиль клапанів, які необхідно закрити, щоб центральний вузол відокремився від усіх розбризкувачів.
Приклад 1