Description

X国有n个城市，编号为1, 2, …, n，城市之间由m条双向道路相连. 小明和小红住在X国不同的城市里，今天小明希望带上最新出的网红甜品去小红家玩，但是这个网红甜品只在少数几个城市才能买到，于是小明想让你帮忙计算一下从家里出发买完甜品之后去小红家的最短路程.

Input

包含不超过20组测试数据。

每组测试数据的第一行包含6个整数n、m、k、s、t、w，其中：

• n表示城市的数量
• m表示城市间道路的数量
• k表示甜品店的数量
• s表示小明所在城市的编号
• t表示小红所在城市的编号
• w表示小明想买的甜品的数量

接下来m行每行包含3个整数a_i、b_i、c_i，表示编号为a_i的城市和编号为b_i的城市之间有一条长度为c_i的双向道路. 接下来k行每行包含2个整数x_j、y_j，表示第j个甜品店所在城市的编号为x_j，该门店一共有y_j个甜品.

数据保证所有城市之间是连通的.

• 3 ≤ n ≤ 10³
• n ≤ m ≤ 10⁴
• 1 ≤ k ≤ min (16,n)
• 1 ≤ c_i ≤ 10³
• 1 ≤ y_j ≤ 10³
• $1 \leq w \leq \sum_{j=1}^{k} y_j$

Output

对于每组测试数据，输出小明从家里出发并在途中买够甜品去小红家最短的总路程.

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

4
5
11