Tax

Jueon studied economics and became a traveling merchant. He trades between two cities and wants to take the route whose total toll is smallest. The cities are joined by two-way roads, and every road charges a toll.

The government announced a tax increase. Raising the tax in one step would cause trouble, so the government raises it in several steps. When the tax rises by $A$, the toll on every road rises by $A$ as well. A tax rise can change the total toll Jueon has to pay.

Help Jueon. Compute the minimum toll before any tax rise, and the minimum toll after each rise.

The first line has three integers $N$ ($2 \le N \le 1000$), $M$ ($1 \le M \le 30000$) and $K$ ($0 \le K \le 30000$): the number of cities, the number of roads, and the number of tax rises, in that order.

The second line has two integers $S$ and $D$ ($1 \le S, D \le N$, $S \ne D$): the number of the starting city and the number of the destination city. Cities are numbered from 1.

Each of the next $M$ lines describes one road with three integers $a$, $b$ ($1 \le a < b \le N$) and $w$ ($1 \le w \le 1000$), meaning that city $a$ and city $b$ are joined by a road whose toll is $w$. Several roads may join the same pair of cities.

Each of the next $K$ lines has one integer $p$ ($1 \le p \le 10$): the first, second, ..., $K$th tax rise, in that order.

The input never asks about a case where $D$ cannot be reached from $S$.

Print the minimum toll before any tax rise on the first line.

On each of the next $K$ lines, print the minimum toll right after the first, second, ..., $K$th tax rise, in that order.

Before the tax rises

After the first tax rise

After the second tax rise