По одной корове с каждой из $N$ ферм ($1 \le N \le 1000$), пронумерованных $1..N$, собираются на большую коровью вечеринку на ферме $X$ ($1 \le X \le N$). Всего $M$ ($1 \le M \le 100,000$) односторонних дорог соединяют пары ферм; прохождение дороги $i$ занимает $T_i$ ($1 \le T_i \le 100$) единиц времени.

Каждая корова должна дойти до вечеринки, а после её окончания вернуться на свою ферму. Все коровы ленивы и выбирают оптимальный маршрут с наименьшим временем. Поскольку дороги односторонние, обратный маршрут может отличаться от пути на вечеринку.

Каково наибольшее среди всех коров время, которое корова должна потратить на путь до вечеринки и обратно?

Входные данные

Считайте ввод из стандартного ввода.

• Строка 1: три целых числа, разделённые пробелами: $N$, $M$ и $X$ соответственно.

Строки $2..M+1$: строка $i+1$ описывает дорогу $i$ тремя целыми числами $A_i$, $B_i$ и $T_i$, разделёнными пробелами. Дорога ведёт от фермы $A_i$ к ферме $B_i$, и её прохождение занимает $T_i$ единиц времени.

Выходные данные

Запишите вывод в стандартный вывод.

• Строка 1: одно целое число — максимальное время ходьбы для одной коровы.

Примеры

Входные данные 1

4 8 2
1 2 4
1 3 2
1 4 7
2 1 1
2 3 5
3 1 2
3 4 4
4 2 3

Выходные данные 1

10

Примечание

Корова $4$ идёт прямо на вечеринку ($3$ единицы) и возвращается через фермы $1$ и $3$ ($7$ единиц), затрачивая всего $10$ единиц времени.

Источник задачи: USACO 2007 February Silver