题目描述

你自幼生活在冒险者大陆，而你的父亲是一位在多年前名扬四方的勇者。 如今你刚刚成年，终于获得了外出冒险的资格。为了提升实力、证明自己的成长，你决定踏上旅途。

冒险者大陆共有 $n$ 个地区，编号为 $1 \sim n$，它们由 $m$ 条双向道路连接。第 $i$ 条道路连接编号为 $u_i$ 和 $v_i$ 的地区，长度为 $w_i$ 米。 保证从任意地区出发，都可以通过若干条道路到达任意另一个地区。

在这些地区中有 $k$ 处为试炼之地，它们被划分为 $L$ 个等级， 每个等级至少存在一处试炼之地。 你抵达一处试炼之地后，可以选择挑战并完成试炼，也可以选择不进行挑战。 然而，若你想挑战等级为 $j$ 的试炼之地，则必须确保自己此前已经通关过至少一处等级为 $j - 1$ 的试炼之地； 特别地，等级为 $1$ 的试炼之地可在任意时刻直接挑战。

你从家乡所在的地区出发，希望最终通关至少一处等级为 $L$ 的试炼之地。 在满足规则的前提下，你想使行走总路程尽可能短。请计算你所需经过的最短路程。

输入格式

第一行包含一个整数 $t$ ($1 \leq t \leq 100$) --- 测试数据的组数。以下是每组测试数据的描述。

第一行包含三个整数 $n, m, k, L, s$ ($2 \leq n \leq 5 \cdot 10^4, 1 \leq s \leq n, n - 1 \leq m \leq 10^5, 1 \leq k \leq n - 1, 1 \leq L \leq \min(10, k)$) --- 地区数量、道路数量、试炼之地的数量、试炼之地的等级数量以及家乡所在的地区。

接下来 $m$ 行，每行包含三个整数 $u_i, v_i, w_i$ ($1 \leq u_i, v_i \leq n, 1 \leq w_i \leq 10^9$) --- 编号为 $u_i$ 和 $v_i$ 的地区之间有一条路，长度为 $w_i$ 米。

再接下来 $k$ 行，每行包含两个整数 $u_i, l_i$ ($1 \leq u_i \leq n, 1 \leq l_i \leq L$) --- 试炼之地所在的地区编号以及该试炼之地的等级，保证

• $u_i$ 两两不同。
• $u_i \neq s$。
• 每个等级至少存在一处试炼之地。

保证所有测试数据的 $n$ 之和不超过 $5 \cdot 10^4$，$m$ 之和不超过 $10^5$。

输出格式

对于每组测试数据，输出一个整数，表示最短总路程。

样例

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

7
5