Рома изучал экономику и стал торговцем. Он путешествует между двумя городами, стараясь выбрать маршрут с наименьшей платой за проезд. Города соединены дорогами с двусторонним движением, и за проезд по каждой из них взимается плата.
Сейчас правительство объявило о повышении налогов. Повышение налогов сразу приведет к проблемам, поэтому правительство повышает их поэтапно. Если налог увеличится на $$$A$$$, то плата за проезд по всем дорогам увеличится на $$$A$$$.
Помогите ему найти первоначальную минимальную плату за проезд и минимальную плату за проезд после каждого увеличения налогов.
В первой строке даны три целых числа $$$N (2 ≤ N ≤ 1 000), M (1 ≤ M ≤ 30 000)$$$ и $$$K (0 ≤ K ≤ 30 000)$$$. Они обозначают количество городов, количество дорог и количество повышений налогов, соответственно.
Во второй строке даны два целых числа $$$S$$$ и $$$D (1 ≤ S, D ≤ N, S \ne D)$$$. Это номера городов отправления и прибытия, соответственно. Города нумеруются в единичной индексации.
В следующих $$$M$$$ строках даны три целых числа $$$a, b (1 ≤ a ≤ N, 1 ≤ b ≤ N, a \ne b), w (1 ≤ w ≤ 1 000)$$$, каждое из которых представляет собой информацию о дороге. Это означает, что город $$$a$$$ и город $$$b$$$ соединены дорогой с платой за проезд $$$w$$$.
В следующих $$$K$$$ строках даны повышения налогов. В каждой строке дано $$$p (1 ≤ p ≤ 10)$$$. Первое, второе и $$$K$$$-ое повышение соответственно.
Гарантируется, что существует путь из $$$S$$$ в $$$D$$$.
В первой строке выведите минимальную плату за проезд до увеличения налога.
Со второй строки в каждой из следующих $$$K$$$ строк выведите минимальную плату за проезд после первого, второго, ..., $$$K$$$-го увеличения налога.
Решение, которое работает при $$$N \times M \times K \le 10^7$$$ получает 50 баллов.
Решение, которое работает при $$$K \le 10$$$ получает 20 баллов.
3 3 2 1 3 1 3 5 1 2 1 2 3 2 1 2
3 5 8
