출퇴근

윤이는 유니마을에 사는 주민이다. 유니마을은 $1$번부터 $N$번까지 번호가 붙은 $N$개의 건물로 이루어져 있다. 윤이는 $A$번 건물에 살고 있고, $B$번 건물에 있는 회사로 매일 출퇴근한다.

유니마을의 구조는 다음과 같다. $N$개의 건물을 잇는 $M$개의 양방향 도로 $R_i$가 있고, 도로를 적절한 순서로 이용하면 임의의 두 건물 사이를 이동할 수 있다. 도로 $R_i$는 서로 다른 $U_i$번 건물과 $V_i$번 건물을 잇고, $R_i$를 지나는 데 $T_i$만큼의 시간이 걸린다. 한 쌍의 건물을 직접 잇는 도로는 최대 하나이다.

그러던 어느 날 윤이는 자신이 마법을 쓰면 교통 상황을 바꿔서 각 도로를 지나는 데 드는 시간을 바꿀 수 있다는 것을 알게 되었다. 윤이는 마법을 최대 $K$번 쓸 수 있는데, 마법을 $k$번 사용하고 나면 모든 $i$에 대해 도로 $R_i$를 지나는 데 걸리는 시간이 $T_{i, k}$가 된다. 윤이는 건물에 있을 때만 마법을 쓸 수 있고, 도로를 지나는 중에는 마법을 쓸 수 없다.

윤이는 마법을 적절히 활용해서 최단 시간으로 회사에 도착하려고 한다. 윤이를 도와 회사에 도착하는 데 필요한 최단 시간을 구하시오.

입력의 첫 줄에 $N$과 $M$, 그리고 $A$와 $B$가 주어진다.

다음 $M$개의 줄에 걸쳐 $U_i, V_i, T_i$가 공백을 사이에 두고 주어진다. $(1 \le i \le M)$

다음 줄에 $K$가 주어진다.

다음 $K$개 줄 중 $k$번째 줄에는 $T_{1, k}, T_{2, k}, \cdots, T_{M, k}$가 공백을 사이에 두고 주어진다. $(1 \le k \le K)$

윤이가 마법을 적절히 활용했을 때 회사에 도착하는 데 걸리는 최단 시간을 출력한다.

• $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$