The country - Ajobdesh has a lot of problems in traffic system. As the Govt. is very clever (!), they made a plan to use only one way roads. Two cities s and t are the two most important cities in the country and mostly people travel from s to t. That's why the Govt. made a new plan to introduce some new one way roads in the traffic system such that the time to travel from s to t is reduced.

But since their budget is short, they can't construct more than d roads. So, they want to construct at most d new roads such that it becomes possible to reach tfrom s in shorter time. Unluckily you are one living in the country and you are assigned this task. That means you will be given the existing roads and the proposed new roads, you have to find the best path from s to t, which may allow at most d newly proposed roads.

Input

Input starts with an integer T (≤ 30), denoting the number of test cases.

Each case starts with a line containing four integers n (2 ≤ n ≤ 10000), m (0 ≤ m ≤ 20000), k (0 ≤ k ≤ 10000), d (0 ≤ d ≤ 10) where n denotes the number of cities, m denotes the number of existing roads and k denotes the number of proposed new roads. The cities are numbered from 0 to n-1 and city 0 is denoted as s and city (n-1) is denoted as t.

Each of the next m lines contains a description of a road, which contains three integers ui vi wi (0 ≤ ui, vi < n, ui ≠ vi, 1 ≤ wi ≤ 1000) meaning that there is a road from ui to vi and it takes wi minutes to travel in the road. There is at most one road from one city to another city.

Each of the next k lines contains a proposed new road with three integers ui vi wi(0 ≤ ui, vi < n, ui ≠ vi 1 ≤ wi ≤ 1000) meaning that the road will be from ui to viand it will take wi minutes to travel in the road. There can be at most one proposed road from one city to another city.

Output

For each case, print the case number and the shortest path cost from s to t&nbs***bsp;"Impossible" if there is no path from s to t.

Sample Input

2

4 2 2 2

0 1 10

1 3 20

0 2 5

2 3 14

2 0 1 0

0 1 100

Sample Output

Case 1: 19

Case 2: Impossible

Note

Dataset is huge, use faster I/O methods.

题目大意:

输入n,m,k,d 分别表示有n个城市，m条道路，现在预计要修k条道路。问 从 0号城市到n-1号城市 在最多使用d条新修道路的前提下，最少花费多少时间。

题目思路：

wa飞了...刚开始思路不对，以为是 在求解最短路的过程中增加一个条件判断，结果发现不对。后来在课上想了一波,思路如下：

注意到d很小，也就是说可以从d下手即可以分层，分层建图应该很简单，关键想清楚层与层之间的含义，首先每层之间应该保持第一次层的权值不变。层与层之间 的如为单向道路，每往下走一层代表，使用了一次新建的道路。最后看每一层的n点最短路的最小值即可。具体看图(样例)：

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

由此我们看出如果样例最多使用一条路径可有选择：5 20 或者 10 14  所以 24

还有一个坑点：单向边！！！

AC：

/***
Status
Accepted
Time
401ms
Memory
30540kB
Length
2035
Lang
C++
Submitted
2019-09-25 16:20:04
Shared
RemoteRunId
1589874
Select Code
***/
#include <bits/stdc++.h>
#include<stdio.h>
#include <string.h>
#include<algorithm>
#pragma GCC optimize(2)
typedef long long ll;
const int mod=998244353;
const int maxn=1e6+5;
const ll INF=10000000000000005;
using namespace std;
ll n,m,p,lm;
inline int read()
{
    int x=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
    return x*f;
}
int head[maxn];
ll dis[maxn];
bool vis[maxn];
struct node{
    int e,next;
    ll w;
}edge[maxn];
ll cnt=0;
void addedge(int u,int v,ll w)
{
    edge[cnt]=node{v,head[u],w};
    head[u]=cnt++;
}
void spfa()
{
    queue<int>q;
    for(int i=0;i<=(lm+1)*n;i++) dis[i]=INF,vis[i]=false;
    dis[1]=0;vis[1]=true;
    q.push(1);
    while(!q.empty())
    {
        int u=q.front();q.pop();vis[u]=false;
        for(int i=head[u];~i;i=edge[i].next)
        {
            int e=edge[i].e;
            if(dis[e]>dis[u]+edge[i].w)
            {
                dis[e]=dis[u]+edge[i].w;
                if(!vis[e])
                {
                    vis[e]=true;
                    q.push(e);
                }
            }
        }
    }
}
int main()
{
    int cas=0;
    int T;scanf("%d",&T);
    while(T--)
    {
        cnt=0;
        memset(head,-1,sizeof(head));
        scanf("%lld%lld%lld%lld",&n,&m,&p,&lm);
        for(int i=1;i<=m;i++)
        {
            int x,y;ll z;
            scanf("%d%d%lld",&x,&y,&z);x++;y++;
            for(int k=0;k<=lm;k++)
                addedge(k*n+x,k*n+y,z);
        }
        for(int i=1;i<=p;i++)
        {
            int x,y;ll z;
            scanf("%d%d%lld",&x,&y,&z);x++;y++;
            for(int k=1;k<=lm;k++)
                addedge((k-1)*n+x,k*n+y,z);
        }
        spfa();
        ll res=dis[n];
        for(int i=1;i<=lm;i++)
            res=min(res,dis[i*n+n]);
        printf("Case %d: ",++cas);
        if(res==INF) printf("Impossible\n");
        else printf("%lld\n",res);
    }
    return 0;
}
/***
4 2 2 1
0 2 10
2 3  20
0 2 5
2 3 14
***/

总结：看了一个小时之后，才把思路转到分层最短路上，这一波有点亏呀，不过也贴个博客当教训了