Commute

Yun lives in Uni Village. Uni Village has $N$ buildings numbered $1$ through $N$. Yun lives in building $A$ and commutes every day to the company in building $B$.

Uni Village has the following structure. There are $M$ bidirectional roads $R_i$ connecting the $N$ buildings, and by using the roads in a suitable order one can travel between any two buildings. Road $R_i$ connects two distinct buildings $U_i$ and $V_i$, and traversing $R_i$ takes $T_i$ time. There is at most one road directly connecting a given pair of buildings.

One day, Yun learned that by casting magic he can change the traffic conditions and thus change the time needed to traverse each road. Yun can cast magic at most $K$ times, and after casting magic $k$ times, the time needed to traverse road $R_i$ becomes $T_{i, k}$ for every $i$. Yun can cast magic only while he is in a building, and he cannot cast magic while traversing a road.

Yun wants to use magic appropriately to reach the company in the shortest time. Help Yun find the shortest time needed to reach the company.

The first line of the input contains $N$, $M$, $A$, and $B$.

The next $M$ lines contain $U_i, V_i, T_i$ separated by spaces. $(1 \le i \le M)$

The next line contains $K$.

Of the next $K$ lines, the $k$-th line contains $T_{1, k}, T_{2, k}, \cdots, T_{M, k}$ separated by spaces. $(1 \le k \le K)$

Print the shortest time needed for Yun to reach the company when he uses magic appropriately.

• $2 \le N \le 1,000$
• $N-1 \le M \le 2,000$
• $M \le N(N-1)/2$
• $1\le A, B, U_i, V_i\le N, A\ne B, U_i \ne V_i$
• $0 \le K \le 100$
• $0 \le T_i, T_{i,k} < 10^9$