출퇴근

윤이는 유니마을에 거주하는 주민이다. 유니마을은 $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$