Катеринка

Обмеження: 2 сек., 256 МіБ

Зеник та Марічка живуть в країні, яка має \(n\) містечок та \(m\) двосторонніх доріг між ними, причому дорога з номером \(i\) з’єднує містечка з номерами \(x_i\) та \(y_i\) та має довжину \(d_i\).

Зеник живе в містечку з номером \(v\), а Марічка — в містечку з номером \(u\). Зеник хоче приїхати в гості до Марічки. Проте, по дорозі він планує заїхати до Катеринки, яка живе в містечку з номером \(c\) (не подумайте нічого поганого про Зеника, Катеринка — просто подруга).

Зеник та Марічка часто переїжджають, а Катеринка завжди живе в одному і тому ж містечку. Вам відомий номер містечка \(c\), в якому проживає Катеринка, а також \(k\) пар чисел \(v_i\), \(u_i\) — номери містечок де проживають, відповідно, Зеник та Марічка. Для кожної такої пари вам необхідно сказати, яку найменшу відстань Зенику необхідно подолати, щоб добратися зі свого дому (вершини \(v_i\)) спершу до Катеринки (вершини \(c\)), а потім до Марічки (вершини \(u_i\)). Зверніть увагу, що Зенику дозволено використовувати одну і ту ж дорогу декілька разів, а також заїжджати до якогось містечка більше одного разу.

Вхідні дані

У першому рядку задано чотири цілі числа \(n\), \(m\), \(q\), \(c\) — кількість вершин, кількість ребер, кількість запитів, а також номер містечка, в якому проживає Катеринка.

Наступні \(m\) рядків містять опис ребер. Кожен з них містить три цілі числа \(x_i\), \(y_i\), \(d_i\) — кінці ребра та його довжина.

Наступні \(q\) рядків містять варіанти початкової та кінцевої вершин на шляху. Кожен з них містить два цілі числа \(v_i\), \(u_i\) — початкова і кінцева вершини.

Вихідні дані

Вам необхідно вивести \(q\) рядків, в \(i\)-му з яких необхідно вивести одне ціле число — найменшу довжину шляху, який починається у вершині з номером \(v_i\), закінчується у вершині з номером \(u_i\), і проходить через вершину \(c\).

Обмеження

\(1 \le n, m, q \le 2 \cdot 10^5\),

\(1 \le x_i, y_i, v_i, u_i, c \le n\),

\(0 \le d_i \le 10^3\),

існує шлях між кожною парою вершин в графі.

Приклади

Вхідні дані (stdin) копіювати	Вихідні дані (stdout) копіювати
4 5 3 1 1 2 1 2 3 3 3 1 1 3 4 4 1 4 10 4 3 2 3 1 4	6 2 5