暂无测试数据。

Description

为了尽快摆脱 \(\text{Volk}\) 的追击，\(\text{Scarral}\) 决定去迷宫。

---

迷宫中有 \(n\) 个小屋（编号 \(1\) ~ \(n\)），小屋间共有 \(m\) 条通道，每条通道长度**不一定**相同，第 \(i\) 个通道连接着编号为 \(u_i\) 和 \(v_i\) 的小屋，长度为 \(w_i\)。\(\text{Scarral}\) 刚进入迷宫时在 \(s\) 号小屋，出口在 \(t\) 号小屋。

同时，\(\text{Scarral}\) 还带了 \(k\) 个便携式传送器，每个传送器都能将 \(\text{Scarral}\) 直接（不用花时间）送至编号在 \(\left[now-r, now+r\right]\) （\(now\) 为当前小屋编号）区间内的小屋里。

为了逃出迷宫，\(\text{Scarral}\) 急忙用 \(\text{Wechat}\) 联系了作为 \(\text{OIer}\) 的你，请你帮他找出最少需要经过多少路程。如果能算出来，帮 \(\text{Scarral}\) 摆脱危险，他将感激不尽。

Input

第 \(1\) 行 \(4\) 个正整数 \(n,m,k,r\)。
第 \(2\) 行至第 \(m+1\) 行，每行 \(3\) 个正整数 \(u_i,v_i,w_i\)。
第 \(m+1\) 行 \(2\) 个正整数 \(s,t\)。

Output

\(1\) 个整数答案，表示最短路程。

Sample

Sample input

待填坑

Sample output

待填坑

Hint

数据范围如下：

测试点编号	\(n\)	\(m\)	\(k\)	特殊性质
\(1\) ~ \(5\)	\(\leq 5\)	\(\leq 10\)	\(\leq 3\)	无
\(6\) ~ \(10\)	\(\leq 10^5\)	\(\leq 2\times 10^5\)	\(\leq 5\)	A
\(11\) ~ \(13\)	\(\leq 10^5\)	\(\leq 2\times 10^5\)	\(\leq 20\)	B
\(14\) ~ \(20\)	\(\leq 10^5\)	\(\leq 2\times 10^5\)	\(\leq 20\)	无

特殊性质A：\(r\leq 3\)；

特殊性质B：\(r=0\)。