В туристическом городе есть n интересных мест, пронумерованных от 1 до n. Турист начинает маршрут в месте 1 и хочет добраться до места n.

По городу можно перемещаться двумя способами:

• по пешим тропам;
• на платных автобусах.

Каждая пешая тропа соединяет два места u и v и позволяет пройти между ними в обоих направлениях за w минут.

Каждый автобусный рейс позволяет проехать из места u в место v за t минут, заплатив c монет. Автобусные рейсы ориентированные, то есть воспользоваться ими можно только в указанном направлении.

У туриста есть не более B монет, которые он может потратить на автобусные поездки. Требуется найти минимальное суммарное время, за которое можно добраться из места 1 в место n, если общие расходы на автобусы не превышают B.

Если добраться невозможно, выведите -1.

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

Первая строка содержит два целых числа n и B — количество мест в городе и максимальный бюджет на автобусные поездки.

Во второй строке содержится целое число p — количество пеших троп.

В следующих p строках содержатся описания пеших троп в формате u v w, где:

• u и v — места, которые соединяет тропа;
• w — время прохода по тропе в минутах.

Следующая строка содержит целое число q — количество автобусных рейсов.

В следующих q строках содержатся описания автобусных рейсов в формате u v t c, где:

• u — место отправления;
• v — место прибытия;
• t — время поездки в минутах;
• c — стоимость поездки в монетах.

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

Выведите одно целое число — минимальное время пути из места 1 в место n при условии, что суммарные расходы на автобусы не превышают B.

Если такого пути не существует, выведите -1.

Ограничения

• 2 <= n <= 50000
• 0 <= B <= 1000
• 0 <= p <= 200000
• 0 <= q <= 200000
• 1 <= u, v <= n
• 1 <= w, t <= 100000
• 1 <= c <= 1000

Примеры

Пример 1

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

2 0
1
1 2 7
0

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

7

Пример 2

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

3 1
2
1 2 10
2 3 10
3
1 3 4 1
1 2 1 1
2 3 1 1

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

4