题号：NC214409
时间限制：C/C++/Rust/Pascal 1秒，其他语言2秒
空间限制：C/C++/Rust/Pascal 256 M，其他语言512 M
64bit IO Format: %lld
时间限制：C/C++/Rust/Pascal 1秒，其他语言2秒
空间限制：C/C++/Rust/Pascal 256 M，其他语言512 M
64bit IO Format: %lld
题目描述
生者困于此地，死者方可离开
夜之城由n个节点组成，某些节点之间可能会有单向道路，这些道路有m条，我们称它们为旧路，由于2070年的公司战争，现增修了A条新路。每条旧路有一个权值c，代表通过这条道路所需要的体力，每条新路也有一个权值，不过是变化的。
以第i条新路为例，一开始其权值为
，若总共经过了j条新路，其权值就会变成
（在完全通过一条新路才会变）。不会存在两条旧路连接相同的两个地标，也不会存在两条新路连接相同的两个地标。
V位于1号点，现在V需要通过恰好k条旧路和B条新路（都可以重复经过），并最终停在任意位置。V希望知道完成这件任务最少需要消耗多少体力。
以第i条新路为例，一开始其权值为
V位于1号点，现在V需要通过恰好k条旧路和B条新路（都可以重复经过），并最终停在任意位置。V希望知道完成这件任务最少需要消耗多少体力。
输入描述:
输入第一行为五个正整数n,m,k,A,B
接下来m行，每行三个整数x,y,c，表示从x到y有一条权值为c的旧路。
接下来A行，每行前两个整数x,y，表示从x到y有一条新路，接下来B个整数，为。
输出描述:
输出仅一行，一个正整数，表示最小的体力。
如果无法完成任务，请输出-1。