• Городское метро
  METRO

Îïèñàíèå
Метро города A насчитывает N станций M линий. Каждой станции метро присвоен свой номер от 1 до N. Описание i-линии метро представляет собой станции (a₁,...,a_ki). Эта запись означает, что данная линия идет от станции a₁ до станции a_ki с промежуточными остановками a₂,...,a_ki-1, причем именно в указанном порядке. Если линия метро соединяет станции с номерами a и b, то по данной линии можно проехать как со станции a на станцию b, так и со станции b на станцию a за одинаковое время. Если две линии метро пересекаются на одной станции, то на ней можно сделать пересадку с одной линии на другую. Время пересадки одинаково для всех станций

Çàäà÷à
Требуется создать программу METRO для определения кратчайшего по времени пути проезда от одной станции метро до другой


Формат входных данных
Входной файл METRO.DAT содержит следующую последовательность строк. В первых трех строках должны быть записаны соответственно:

• целое число N - количество станций метро (N<=30)

• целое число M - количество линий метро (M<=30)

• время пересадки (положительное действительное число)

Каждая из последующих 3·M строк должна содержать следующую информацию:

• строка с номером 3·(i-1)+1 - целое число K_i, определяющее количество станций на i-й линии;  

• строка с номером 3·(i-1)+2 - описание i-линии метро в виде последовательности (a₁,...,a_ki), где a₁, ... ,a_ki определяют номера станций этой линии;

• строка с номером 3·(i-1)+3 - последовательность (b₁,...,b_ki-1) из (K_i-1) чисел, где b₁ определяет время проезда по этой линии от станции a₁ до a₂,...,b_ki-1 время проезда от станции a_ki-1 до a_ki

Последняя строка входного файла должна содержать разделенные пробелами числа x,a,y,b, где (x, a) - номер станции и номер линии метро, определяющие начало пути, а (y, b) - номер станции и номер линии метро, определяющие его конец.  

Формат выходных даннных
Выходной файл METRO.SOL представляется в виде последовательности строк, задающих искомый путь. Каждая i-ая строка содержит пару чисел вида (a_i,b_i), где ai-номер станции, bi-номер линии метро. Переход с одной линии метро на другую также должен быть отображен

Например:

METRO.DAT  
5  
2  
10  
3  
1  4  5  
1  1  
3  
2  4  3  
2  3  
1  1  2  2

METRO.SOL
1  1  
4  1  
4  2  
2  2