Помогите вывести ответ по условию, не получается его вывести, пожалуйста.

В одном феодальном государстве средневековой Европы было N городов и M дорог, каждая из которых соединяла некоторые два города. Каждая дорога принадлежала правителю одного из городов (не обязательно из тех, которые она соединяла). Однажды правитель города S решил объявить войну правителю города T. Перед ним сразу же встала нелёгкая задача: как довести армию до города T. Правитель каждого города требует плату за проход войск через его город. Кроме того, правитель города S может перемещать войска только по дорогам, которые принадлежат ему. При этом он может купить любую дорогу у её владельца за определённую плату (даже если владелец — правитель города T). К сожалению, все деньги из казны города S были потрачены на предыдущий неудачный военный поход, поэтому сначала правителю придётся продать некоторые свои дороги (разумеется, после этого он не сможет провести по ним войска). Помогите правителю выяснить, какие дороги следует продать, а какие купить, чтобы довести войска от города S до города T и оплатить проход через все промежуточные города. Все операции продажи и покупки дорог надо осуществить до начала похода, пока правители других городов не догадались о воинственных намерениях правителя города S. Формат входных данных Первая строка содержит целые числа N и M — количество городов и дорог соответственно (2 ≤ N ≤ 2000, 1 ≤ M ≤ 50000). Города нумеруются от 1 до N,города S и T имеют номера 1 и N соответственно. В каждой из следующих N строк находится по одному целому числу Ri — плата за проезд через город i (0 ≤ Ri ≤ 10000, R1 = RN =0). Следующие M строк содержат описания дорог. Дорога описывается четырьмя целыми числами: Ai, Bi, Pi и Ci,где Ai и Bi —номера городов, которые соединяет дорога (Ai ≠ Bi); Pi — номер города, правителю которого она принадлежит; Ci — её стоимость (1 ≤ Ci ≤ 10000). По дороге можно перемещаться в обоих направлениях. Любые два города соединены не более чем одной дорогой. Формат выходных данных В первой строке выведите список дорог, необходимых для продажи, в следующем формате: сначала число дорог, а затем их номера. Дороги нумеруются с единицы в том порядке, в котором они заданы на входе. Во второй строке выведите список дорог, необходимых для покупки, в том же формате. В третьей строке выведите маршрут похода — номера городов в порядке следования войска. Если решений несколько, выведите любое. Если решения нет, выведите число −1.

var i, j, cash, mi, n, m: integer;
r, prev: array [1..2000] of integer;
z: array [1..2000, 1..2000] of integer;
a, b, c, p, s: array [1..50000] of integer;
d: array [0..2000] of integer;
u: array [1..2000] of boolean;
q: array [1..50000, 1..50000] of byte;

begin

read(n, m);
for i := 1 to n do begin
read(r[i]);
end;
for i := 1 to n do begin
for j := 1 to n do begin
z[i][j] := maxlongint div 2;
end;
end;

cash := 0;
for i := 1 to m do begin
read(a[i], b[i], p[i], c[i]);
if p[i] = 1 then begin
s[i] := -1;
cash := cash + c[i];
end;
q[a[i], b[i]] := i;
q[b[i], a[i]] := i;
z[a[i], b[i]] := c[i] + r[b[i]];
z[b[i], a[i]] := c[i] + r[a[i]];
end;

for i := 0 to n do begin
d[i] := maxlongint div 2;
end;
d[0] := maxlongint div 2;
d[1] := 0;
for i := 1 to n do begin
mi := 0;
for j := 1 to n do begin
if not u[j] and (d[j] < d[mi]) then begin
mi := j;
end;
end;
u[mi] := true;
for j := 1 to n do begin
if d[j] > d[mi] + z[mi][j] then begin
d[j] := d[mi] + z[mi][j];
prev[j] := mi;
end;
end;
end;

if cash < d[n] then begin
writeln(-1);
exit;
end;
i := n;
j := prev[n];
while j <> 0 do begin
inc(s[q[i][j]]);
i := prev[i];
j := prev[j];
end;

end.