T823231 遗迹符文（runes）

探险家艾莉丝来到一座古代遗迹。遗迹有 $n$ 个房间，编号为 $1,2,\ldots,n$。房间之间有 $m$ 条双向通道，通过每条通道都需要付出一定的代价。 遗迹中还有 $k$ 块符文石，编号为 $1,2,\ldots,k$。第 $i$ 块符文石位于房间 $s_i$，它对应一道连接房间 $a_i$ 和 $b_i$ 的传送门。该传送门生效时，可以从 $a_i$ 前往 $b_i$，也可以从 $b_i$ 前往 $a_i$，每次使用的代价均为 $c_i$。传送门的端点不一定是符文石所在的房间。 艾莉丝的法器只能让一道传送门生效。法器会按激活的先后顺序记录尚未撤销的符文石，只有其中**最后激活、尚未撤销的那一块**所对应的传送门生效。 艾莉丝从房间 $S$ 出发，初始时没有激活过任何符文石。她可以执行以下操作： - **沿通道移动**：沿一条普通通道前往另一端的房间，支付该通道的代价。普通通道始终可以使用，不受符文状态影响。 - **使用传送门**：若有生效的传送门，且当前位于它的一个端点，则可以支付对应的 $c_i$，到达另一端。只要这道门仍生效，就可以使用多次。 - **激活符文石**：当前位于 $s_i$ 且第 $i$ 块符文石从未被激活过时，可以免费激活它。它成为新的最后一块，之前生效的传送门暂时失效。激活不会改变当前所在房间。 - **撤销激活**：若还有尚未撤销的符文石，可以在**任意房间**免费撤销最后激活的那一块。若记录中还有更早的符文石，则其中最后一块的传送门恢复生效；否则没有生效的传送门。撤销也不会改变当前所在房间。 每块符文石一生只能被激活一次。被撤销的符文石不能再次激活；暂时被后来的符文覆盖，也不代表它可以重新激活。 请计算艾莉丝从 $S$ 到达 $T$ 的最小总代价。到达 $T$ 时不要求撤销已经激活的符文石。如果无法到达，输出 $-1$。 本题有多组测试数据，不同组之间的图和符文状态相互独立。

第一行包含一个正整数 $Q$，表示测试数据组数。 对于每组测试数据： 第一行包含五个整数 $n,m,k,S,T$。 接下来 $m$ 行，每行包含三个整数 $u,v,w$，表示房间 $u$ 与房间 $v$ 之间有一条代价为 $w$ 的双向通道。 接下来 $k$ 行，第 $i$ 行包含四个整数 $s_i,a_i,b_i,c_i$，依次表示第 $i$ 块符文石的位置、传送门的两个端点和使用代价。$k=0$ 时没有这部分输入。

对于每组测试数据，输出一行一个整数，表示从 $S$ 到 $T$ 的最小总代价；无法到达时输出 $-1$。

### 样例解释 只沿普通通道从房间 $1$ 走到房间 $4$，代价为 $5+5+5=15$。 更优的方案是：先从房间 $1$ 走到房间 $2$，支付 $5$；在房间 $2$ 免费激活符文石；再沿普通通道返回房间 $1$，支付 $5$；最后使用生效的传送门从房间 $1$ 到房间 $4$，支付 $1$。总代价为 $5+5+1=11$。 注意：激活符文石不会直接把艾莉丝从房间 $2$ 传送到出口，使用传送门前仍需到达它的端点。 ## 样例 2 见 `考生目录/runes/runes2.in` 与 `考生目录/runes/runes2.ans`。该样例满足测试点 $1\sim4$ 的约束。 ## 样例 3 见 `考生目录/runes/runes3.in` 与 `考生目录/runes/runes3.ans`。该样例满足测试点 $5\sim8$ 的约束。 ## 样例 4 见 `考生目录/runes/runes4.in` 与 `考生目录/runes/runes4.ans`。该样例满足测试点 $9\sim12$ 的约束。 ## 样例 5 见 `考生目录/runes/runes5.in` 与 `考生目录/runes/runes5.ans`。该样例满足测试点 $13\sim16$ 的约束。 ## 样例 6 见 `考生目录/runes/runes6.in` 与 `考生目录/runes/runes6.ans`。该样例满足测试点 $17\sim20$ 的约束。 ## 样例 7 见 `考生目录/runes/runes7.in` 与 `考生目录/runes/runes7.ans`。该样例满足测试点 $17\sim20$ 的约束。 ## 样例 8 见 `考生目录/runes/runes8.in` 与 `考生目录/runes/runes8.ans`。该样例满足测试点 $17\sim20$ 的约束。 ## 数据范围 对于所有数据，保证： - $1\le Q\le10$。 - 同一输入文件中，所有数据的 $n$ 之和不超过 $2\times10^5$，$m$ 之和不超过 $4\times10^5$。 每组数据均满足： - $1\le n\le10^5$，$0\le m\le2\times10^5$，$0\le k\le\min(7,n)$。 - $1\le S,T,u,v,s_i,a_i,b_i\le n$，$u\ne v$，$a_i\ne b_i$。 - 各 $s_i$ 互不相同。符文石位置可以与传送门端点重合，不同传送门也可以共用端点。 - $1\le w,c_i\le10^9$。 - 普通通道可以连接同一对房间多次，不保证所有房间互相连通。允许 $S=T$。 | 测试点编号 | 附加限制（每组均满足） | | ---------- | --------------------------- | | $1\sim4$ | $n\le10$，$m\le20$，$k\le3$ | | $5\sim8$ | $k=0$ | | $9\sim12$ | $k=1$ | | $13\sim16$ | $k\le3$ | | $17\sim20$ | 无 |