Берляндия состоит из \(n\) городов, некоторые из которых соединены двусторонними дорогами таким образом, что между каждой парой вершин существует ровно один путь, проходящий по каждой дороге не более одного раза. Каждая дорога характеризуется своей длиной. Города пронумерованы от \(1\) до \(n\).
Время пути между некоторыми городами \(v\) и \(u\) — это суммарная длина дорог на кратчайшем пути из \(v\) в \(u\).
Два наиболее важных города Берляндии имеют номера \(1\) и \(n\).
Министерство Транспорта Берляндии решило построить ровно одну новую дорогу, чтобы разгрузить движение между самыми важными городами. Однако многие уже привыкли к текущему времени пути между самыми важными городами, поэтому новая дорога не должна его сильно изменить.
Новая дорога может быть построена только между такими городами \(v\) и \(u\), что \(v \neq u\) и \(v\) и \(u\) еще не соединены никакой дорогой.
Они создали планы \(m\) возможных проектов. Каждый проект — это просто длина \(x\) новой дороги.
Поликарп работает главным аналитиком Министерства Транспорта Берляндии, разбираться с этими \(m\) проектами — его задача. Для \(i\)-го проекта он должен выбрать некоторые города \(v\) и \(u\) и построить новую дорогу длины \(x_i\) между ними так, чтобы время пути между самыми важными городами было максимально возможным.
К сожалению, Поликарп совсем не программист, да и никакой аналитик в мире не справится со всеми проектами с помощью лишь ручки и бумаги.
Поэтому он просит вас помочь ему посчитать максимально возможное время пути между самыми важными городами для каждого проекта. Обратите внимание, что \(v\) и \(u\) выбираются независимо для каждого проекта.
Примечание
Сеть дорог из первого примера:
Можно построить дорогу длины \(1\) между городами \(5\) и \(6\), чтобы получить \(83\) в качестве времени пути между \(1\) и \(7\) (\(1 \rightarrow 2 \rightarrow 6 \rightarrow 5 \rightarrow 3 \rightarrow 4 \rightarrow 7\) \(=\) \(18 + 4 + 1 + 12 + 24 + 24 = 83\)). Другие доступные пары городов дадут ответ меньше или равный \(83\).