kejin Game

题号：NC247014
时间限制：C/C++/Rust/Pascal 3秒，其他语言6秒
空间限制：C/C++/Rust/Pascal 512 M，其他语言1024 M
64bit IO Format: %lld

题目描述

给你一个有向无环图代表技能的前置关系。

这张图有 $n$ 个节点， $m$ 条有向边，你想要学会的技能是 $s$ 号技能。现在你每次可以进行以下三种操作中的一种：

1. 花费 $c_i$ 的金钱删去一条边 $a_i,b_i$ 。
2. 花费 $p_i$ 的金钱学会第 $i$ 个技能，但是在学习之前，它的所有前置技能都已经获得。
3. 花费 $q_i$ 的金钱学会第 $i$ 个技能。

请你求出学会 $s$ 号技能的最小花费。

输入描述:

第一行一个表示数据组数
对于每组数据，第一行三个整数
之后行每行三个整数表示有一条到的有向边，删去的代价为
接下来一行个整数表示
接下来一行个整数表示

输出描述:

对于每组数据，输出一行一个整数，表示答案。

示例1

输入

复制

2
5 5 5
1 2 5
1 3 5
2 4 8
4 5 10
3 5 15
3 5 7 9 11
100 100 100 200 200
5 5 5
1 2 5
1 3 5
2 4 8
4 5 10
3 5 15
3 5 7 9 11
5 5 5 50 50

输出

复制

31
26