Description

跳跳虎在外面出去玩忘了时间，现在他需要在最短的时间内赶回家。

跳跳虎所在的世界可以抽象成一个含有 $n$ 个点的图（点编号从 $1$ 到 $n$），跳跳虎现在在 $1$ 号点，跳跳虎的家在 $n$ 号点。

图上一共有 $m$ 条单向边，通过每条边有固定的时间花费。

同时，还存在若干个单向传送通道，传送通道也有其时间花费。

传送通道一般来说比普通的道路更快，但是跳跳虎最多只能使用 $k$ 次。

跳跳虎想知道他回到家的最小时间消耗是多少。

Input Format

第一行输入 $4$ 个整数 $n,m,q,k$。（$n$ 表示点数，$m$ 表示普通道路的数量，$q$ 表示传送通道的数量，$k$ 表示跳跳虎最多使用 $k$ 次传送通道）

接下来 $m$ 行每行 $3$ 个整数 $u,v,w$，表示有一条从 $u$ 到 $v$，时间花费为 $w$ 的普通道路。（$1\le u,v\le n,1\le w\le 10^3$）

接下来 $q$ 行每行 $3$ 个整数 $x,y,z$，表示有一条从 $x$ 到 $y$，时间花费为 $z$ 的传送通道。（$1\le x,y\le n,1\le z\le 10^3$）

Output Format

输出一行一个整数表示最小时间消耗，如果没法回到家输出 $-1$。

Sample

样例输入

5 5 2 1 
1 2 1 
1 3 2 
2 4 2 
3 4 3 
4 5 4 
1 4 1 
2 5 1

样例输出

2

Hint

对于 $30\%$ 的数据，$1\le n\le 500,0\le m,q\le 2000,k=0$；

对于另外 $30\%$ 的数据，$1\le n\le 500,0\le m,q\le 2000,k=1$；

对于 $100\%$ 的数据，$1\le n\le 500,0\le m,q\le 2000,0\le k\le 10^9$。