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

Первая строка содержит целое число N — количество перекачивающих станций, между которыми есть нефтепроводы (1 ≤ N ≤ 10 000). Станции занумерованы от 1 до N. Следующие N строк описывают станции.

i-я строка содержит четвёрку целых чисел a b c d (1 ≤ a ≤ N; 0 ≤ c ≤ b ≤ 10 000; 0 ≤ d ≤ 10⁶), где
a — номер станции, к которой существует нефтепровод от станции i,
b — пропускная способность нефтепровода от i до a в миллионах баррелей в день,
c — текущий поток нефти от i до a в миллионах баррелей в день,
d — количество денег (в рублях), необходимое для увеличения пропускной способноти нефтепровода от i до a на 1 миллион баррелей в день. Может быть не более одного нефтепровода от станции i до станции a, и никакой нефтепровод не соединяет станцию с ней самой.

Четвёрки в одной строке разделяются запятыми, после последней четвёрки стоит точка. Если нефть с i-й станции не перекачивается никуда, то соответствующая строка содержит только один символ ".". Гарантируется, что во входных данных содержится не более 100 000 четвёрок, описывающих нефтепроводы.

Нефть перекачивается зарубежным партнёрам только со станции с номером N. Поток нефти через границу равен потоку, входящему в эту станцию. С этой станции нефть не передаётся другим станциям в описанной системе нефтепроводов. Перекачивающие станции с номерами менее N являются транзитными. Известно, что для каждой транзитной станции входящий поток нефти не больше выходящего потока. Если входящий поток меньше, чем выходящий, то поблизости есть нефтяная скважина, добыча нефти в которой может быть легко увеличена на 1 миллион баррелей в день.

В первой строке выведите минимальную стоимость K такого изменения сети нефтепроводов, что перекачивание нефти зарубежным партнёрам увеличится на 1 миллион баррелей в день. После этого выведите N строк, описывающих поток нефти в трубопроводах после переделки трубопроводов в следующем формате: i-я строка должна содержать список пар a b, разделённых запятыми; a — номер станции, к которой нефть перекачивается со станции i, а b — количество перекачиваемой нефти в миллионах баррелей в день. Каждая из этих строк должна заканчиваться точкой.

Если невозможно достигнуть цели Коляна, выведите единственное слово "Impossible".