Задача F. Истинное наслаждение

Задачу добавил: alef

Успешно сдано решений: 2

Ограничения: время на тест - 5с, память - 256 Мб

Благополучно покинув систему Сириуса, Василий прибыл на планету возле Капеллы. Она понравилась ему намного больше предыдущей - много растительности, привычная влажность воздуха. Да и отшельника искать пришлось совсем недолго. Он жил неподалеку от заброшенной фабрики. Когда-то давно на планете позакрывали почти все фабрики и заводы - чистый воздух, прекрасный климат и красивая природа позволяют безбедно существовать местным жителям за счет туризма.

Отшельник Ли Си Цин осмотрел ноутбук, с легкой улыбкой выслушал рассказ Василия, зачем это все понадобилось и, махнув рукой в сторону здания фабрики, сказал: "Завтра утром схожу в свою мастерскую, все сделаю. Ничего сложного. А сейчас вечер, и это время не стоит тратить на работу. Мы будем сидеть на террасе у моего дома, пить чай и смотреть на закат над океаном. А еще ты расскажешь мне, что новенького на Земле."

Несмотря на то, что Ли Си Цин живет в экологически чистом мире, состав местной воды его не вполне устраивает и он пропускает ее через фильтр собственного изготовления. Фильтр состоит из одинаковых очень высоких цилиндрических сосудов, занумерованных от 1 до N. Некоторые из сосудов попарно соединены тончайшими трубками. Все трубки расположены на разной высоте, но при этом каждая из них строго параллельна полу. В сосуд #1 медленно капает вода. Проходя через систему мембран, расположенных в трубках, она растекается по всем сосудам. Для чая, который Ли Си Цин собрался заварить сейчас, наилучшим образом подходит вода из сосуда #K. Василий обратил внимание, что высота водяного столба в сосуде #K равна H, и теперь его интересует, какое минимально возможное количество воды было залито в систему через сосуд #1. Ваша задача - по заданным связям между сосудами определить это.

Первая строка - целые числа N и M (0 < N, M <= 100000) - количество сосудов и количество связей между ними
В каждой из следующих M строк содержится по три целых числа V1j, V2j, Rj (0 <= Rj <= 10^9) (j = 1, 2, ..., M)- номера сосудов, соединенных трубкой #j, Rj - высота этой трубки над полом.
В следующей строке записано целое число Q (0 < Q <= 100000) - количество запросов
Каждая из следующих Q строк содержит по два числа: Kp и Hp  (1 <= Kp <= N, 0 <= Hp <= 10^9) (p = 1, 2, ... , Q), которые формируются следующим образом.
Для p = 1 число K1 обозначает номер сосуда, в котором наблюдается высота водяного столба H1.
Для p > 1 номер сосуда вычисляется как (Kp + S(p-1)) mod N, где S(p-1) - высота водяного столба в сосуде #1, полученная для предыдущего запроса. Уровень воды в сосуде с этим номером составляет Hp.
Гарантируется, что рано или поздно любой сосуд будет наполняться.

Формат выходного файла output.txt
В каждой из Q строк выходного файла содержится по одному числу Sp (p = 1, 2, ..., Q) - минимально возможное количество воды, залитое в систему, при условии, что в сосуде, определяемом значением Kp, уровень воды составляет Hp.

Решения, правильно работающие при N,M <= 1000, Q = 1, получат не менее 25 баллов
Решения, правильно работающие при N,M <= 100000, Q = 1, получат не менее 50 баллов
Решения, правильно работающие при N,M <= 1000, Q <= 1000, получат не менее 50 баллов


Пример входного файла
5 4
1 2 10
2 3 5
3 4 2
4 5 7
60
1 0
1 1
5 2
4 3
3 4
2 5
1 6
5 7
4 8
3 9
2 10
1 11
2 0
2 1
1 2
5 3
4 4
3 5
2 6
4 7
1 8
5 9
1 10
2 11
3 0
3 1
2 2
1 3
2 4
5 5
3 6
5 7
2 8
1 9
2 10
3 11
4 0
4 1
1 2
5 3
3 4
1 5
4 6
1 7
3 8
2 9
3 10
4 11
5 0
5 1
3 2
2 3
1 4
5 5
4 6
3 7
2 8
3 9
4 10
5 11

Пример выходного файла
0
1
2
3
4
5
6
7
8
9
10
55
0
11
12
13
14
15
28
31
42
46
50
55
0
16
17
21
23
25
28
31
42
46
50
55
0
18
19
21
23
25
28
31
42
46
50
55
0
32
33
34
35
36
37
38
42
46
50
55


Сдать задачу

Задать вопрос жюри по этой задаче