题目描述

有一个国家的道路都是单向的。城市 $0$ 是起点，城市 $n-1$ 是终点。现在已经有一些旧道路，也有一些计划修建的新道路。

一次出行中，最多只能使用 $d$ 条新道路。请在这个限制下，求从城市 $0$ 到城市 $n-1$ 的最短用时。如果无论怎样都无法到达，输出 Impossible。

输入格式

第一行输入测试组数 $T$。

每组数据第一行输入 $n,m,k,d$，分别表示城市数、旧道路数、新道路数以及最多可使用的新道路条数。

接下来 $m$ 行，每行输入 $u_i,v_i,w_i$，表示一条从 $u_i$ 到 $v_i$、耗时 $w_i$ 的旧道路。

接下来 $k$ 行，每行输入 $u_i,v_i,w_i$，表示一条从 $u_i$ 到 $v_i$、耗时 $w_i$ 的候选新道路。

输出格式

对每组数据输出 Case x: ans。如果可达，$ans$ 为最短用时；否则输出 Impossible。

样例

2
4 2 2 2
0 1 10
1 3 20
0 2 5
2 3 14
2 0 1 0
0 1 100

Case 1: 19
Case 2: Impossible

样例说明

数据范围