В первой строке записано целое число n (2 ≤ n ≤ 300) — число городов в Берляндии. Далее в n строках записано по n целых чисел — матрица кратчайших расстояний. j-ое число в i-ой строке — d_i, j, кратчайшее расстояние между городами i и j. Гарантируется, что d_i, i = 0, d_i, j = d_j, i, и заданная матрица является матрицей кратчайших расстояний для некоторого набора двусторонних дорог с целочисленной длиной от 1 до 1000, таким, что по этим дорогам можно доехать из любого города до любого другого.

На следующей строке записано целое число k (1 ≤ k ≤ 300) — число запланированных дорог. В следующих k строках записаны описания запланированных дорог. Каждая дорога описывается тремя целыми числами a_i, b_i, c_i (1 ≤ a_i, b_i ≤ n, a_i ≠ b_i, 1 ≤ c_i ≤ 1000) — a_i и b_i — пара городов, которые соединяет дорога, c_i — длина дороги. Между парой городов может быть несколько дорог, но никакая дорога не соединяет город сам с собой.