Задача S. Торговый караван ≡

Условие

Караван купцов движется из города S в город F. Их маршрут должен пройти через города, соединенные между собой прямыми путями.

Известно, что за проход через отдельно взятый город купцам придется платить некоторую установленную пошлину.

Помимо этого за каждую единицу пути, караван тратит определенное число ресурсов, также выраженных в денежном эквиваленте.

Требуется проложить маршрут, минимизирующий суммарную пошлину и число затраченных ресурсов.

В случае, если существует несколько таких маршрутов, необходимо выбрать тот, который проходит через наибольшее число городов.

Формат входного файла

В начале входного файла "input.txt" указано натуральное N — число городов, за которым следует набор из N целых чисел
P_i — размер пошлины для каждого i-го города.

Далее указано натуральное M, за которым следует ровно M троек целых чисел:
A_j, B_j — номера соседних городов;
W_j — стоимость перехода.

В конце входного файла указаны индексы начального S и конечного F города.

При этом полагается, что нумерация городов начинается с нуля.

Формат выходного файла

Выходной файл "output.txt" должен содержать оптимальный маршрут,
представленный в виде последовательности городов,
через которые он проходит.

Ограничения

2 ≤ N ≤ 1000, 1 ≤ M ≤ (N ⋅ (N − 1)) / 2,

0 ≤ P_i ≤ 10⁶,

0 ≤ (A_j, B_j) < N, A_j ≠ B_j,

0 < W_j ≤ 10⁶

Примеры тестов

6
0 3 5 1 0 0

8
0 2 10
5 4 3
5 1 14
1 3 4
4 1 10
2 3 5
2 1 6
0 5 7

0 1

0
5
4
1

6
0 0 0 1 0 7

8
0 2 10
1 3 4
5 4 3
2 1 10
5 0 7
4 1 12
2 3 5
5 1 6

0 1

0
2
3
1