Катеринка
Limits: 2 sec., 256 MiB
Зеник та Марічка живуть в країні, яка має \(n\) містечок та \(m\) двосторонніх доріг між ними, причому дорога з номером \(i\) з’єднує містечка з номерами \(x_i\) та \(y_i\) та має довжину \(d_i\).
Зеник живе в містечку з номером \(v\), а Марічка — в містечку з номером \(u\). Зеник хоче приїхати в гості до Марічки. Проте, по дорозі він планує заїхати до Катеринки, яка живе в містечку з номером \(c\) (не подумайте нічого поганого про Зеника, Катеринка — просто подруга).
Зеник та Марічка часто переїжджають, а Катеринка завжди живе в одному і тому ж містечку. Вам відомий номер містечка \(c\), в якому проживає Катеринка, а також \(k\) пар чисел \(v_i\), \(u_i\) — номери містечок де проживають, відповідно, Зеник та Марічка. Для кожної такої пари вам необхідно сказати, яку найменшу відстань Зенику необхідно подолати, щоб добратися зі свого дому (вершини \(v_i\)) спершу до Катеринки (вершини \(c\)), а потім до Марічки (вершини \(u_i\)). Зверніть увагу, що Зенику дозволено використовувати одну і ту ж дорогу декілька разів, а також заїжджати до якогось містечка більше одного разу.
Input
У першому рядку задано чотири цілі числа \(n\), \(m\), \(q\), \(c\) — кількість вершин, кількість ребер, кількість запитів, а також номер містечка, в якому проживає Катеринка.
Наступні \(m\) рядків містять опис ребер. Кожен з них містить три цілі числа \(x_i\), \(y_i\), \(d_i\) — кінці ребра та його довжина.
Наступні \(q\) рядків містять варіанти початкової та кінцевої вершин на шляху. Кожен з них містить два цілі числа \(v_i\), \(u_i\) — початкова і кінцева вершини.
Output
Вам необхідно вивести \(q\) рядків, в \(i\)-му з яких необхідно вивести одне ціле число — найменшу довжину шляху, який починається у вершині з номером \(v_i\), закінчується у вершині з номером \(u_i\), і проходить через вершину \(c\).
Constraints
\(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\),
існує шлях між кожною парою вершин в графі.
Samples
| Input (stdin) | Output (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 |
| Element Type | Created | Who | Problem | Compiler | Result | Time (sec.) | Memory (MiB) | # | Actions |
|---|