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

Известна информация о начальной структуре компьютерной сети и времени передачи информации между соответствующими узлами сети. Известно, что если между узлами существует связь, то информация передается наиболее выгодным (быстрым) маршрутом.

После возникновения повреждений сети время передачи информации между некоторыми узлами уменьшилось.

Определите, где следует разместить главный сервер, чтобы время передачи информации от сервера к самому удаленному (тому, к которому информация находит наиболее медленно) узлу сети было бы минимальным.

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

Первая строка содержит два натуральных числа: n (1 ≤ n ≤ 1000) - количество узлов сети и m - количество каналов связи между этими узлами .

В каждой из следующих m строк приведена информация о количестве миллисекунд ci на передачу информации от узла ai к bi в форме трех чисел: ai , bi и ci (1 ≤ ai, bi ≤ n, 1 ≤ i ≤ m).

В следующей строке размещено число k (0 ≤ k ≤ m) - количество каналов связи, в которых уменьшилась скорость передачи информации.

Далее размещены k строк, в каждой из которых приведена информация на сколько уменьшилось время на передачу информации между соответствующей парой узлов в форме трех чисел: xi, yi и zi (1 ≤ xi, yi ≤ n, 1 ≤ i ≤ m), где xi, yi - номера узлов сети, а zi показывает, на сколько миллисекунд увеличилось время передачи информации между узлами xi и yi.

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

Определите, в каком узле сети нужно разместить главный сервер, чтобы время передачи информации от сервера к самому удаленному (тому, к которому информация находит наиболее медленно) узлу сети было бы минимальным. Если сервер можно разместить в нескольких узлах, перечислите номера таких узлов в порядке возрастания.

Пояснение

Сервер следует разместить в пункте 1. Тогда время передачи данных в наиболее отделенный узел 4 будет составлять 25 миллисекунд.