Баобаб
(Время: 5 сек. Память: 128 Мб Сложность: 53%)
«Элементарными называются такие истины, которые человек открывает последними.»
(с) Альбер Камю
Одним осенним вечером Егор прогуливался по ботанической оранжерее Мебибайтного Гибибайтного Универститета. Он повстречал на своём пути недавно открытое особенное дерево – баобаб. Он сразу заметил несколько свойств этого чудесного дерева и сформулировал важную для дальнейших исследований задачу.
Формально, вам дан неориентированный взвешенный граф без кратных ребер и петель, который называется баобабом. Баобаб представляет из себя один или более простых путей, имеющих общее начало в вершине 1 и общий конец в вершине n. Других общих вершин ни у каких двух путей нет. Каждый такой путь состоит из двух или более вершин. Каждое ребро описывается тремя числами u, v и c, которые обозначают ребро весом c между вершинами u и v.
Вам нужно ответить на q запросов — найти минимальный по весу путь от одной вершины до другой. Помогите Егору решить эту непростую задачу!
Входные данные
В первой строке входного файла INPUT.TXT записано три целых числа n, m и q (2 ≤ n ≤ 105; 1 ≤ m < 2×105; 1 ≤ q ≤ 2×105) — количество вершин, ребер и запросов.
В следующих m строках записано по три целых числа u, v, c (1 ≤ u, v ≤ n; 1 ≤ c ≤ 109), описывающие ребра графа.
В следующих q строках записано по два числа x, y (1 ≤ x, y ≤ n), задающие очередной запрос
Выходные данные
В выходной файл OUTPUT.TXT Выведите q целых чисел — ответы на запросы в порядке появления запросов во входных данных.
Пример
| № | INPUT.TXT | OUTPUT.TXT | Пояснение |
|---|
| 1 | 8 9 5
1 2 2
2 3 2
3 4 1
4 8 1
1 5 3
5 6 1
6 8 1
1 7 2
7 8 1
4 7
2 5
4 1
1 8
2 4
| 2 5 4 3 3 |  |
Для отправки решения задачи необходимо зарегистрироваться и авторизоваться!
| 
