#include<bits/stdc++.h>
using namespace std;
 
#define ll long long
#define inf 1e15
vector<pair<pair<ll,ll> ,ll> >edge;
 
ll vis[1005];
ll cost[1005];
 
int main()
{
    ll i,j,n,m,t,a,b,c,p,d,e;
    scanf("%lld",&t);
    for(ll cz=1;cz<=t;cz++){
        printf("Case %lld: ",cz);
            memset(cost,0,sizeof(cost));
        scanf("%lld%lld%lld",&n,&m,&p);
        edge.clear();
 
        for(i=1;i<=m;i++){
            scanf("%lld%lld%lld%lld",&a,&b,&d,&e);
            c=p*e-d;
            edge.push_back(make_pair(make_pair(a,b) ,c));
        }
 
        ll len=edge.size();
        ll u,v,chk=0;
        for(j=1;j<=n;j++)
        for(i=0;i<len;i++){
                u=edge[i].first.first;
                v=edge[i].first.second;
                c=edge[i].second;
 
                if(cost[v]>cost[u]+c){
                    cost[v]=cost[u]+c;
                }
        }
 
        for(i=0;i<len;i++){
                u=edge[i].first.first;
                v=edge[i].first.second;
                c=edge[i].second;
 
                if(cost[v]>cost[u]+c&&vis[u]==0){
                    //cout<<cost[v]<<" "<<v<<endl;
                    cost[v]=cost[u]+c;
                    //cout<<cost[v]<<" "<<v<<endl;
                chk=1;
                }
        }
 
        if(chk==1)printf("YES\n");
        else printf("NO\n");
    }
}

I2luY2x1ZGU8Yml0cy9zdGRjKysuaD4KdXNpbmcgbmFtZXNwYWNlIHN0ZDsKCiNkZWZpbmUgbGwgbG9uZyBsb25nCiNkZWZpbmUgaW5mIDFlMTUKdmVjdG9yPHBhaXI8cGFpcjxsbCxsbD4gLGxsPiA+ZWRnZTsKCmxsIHZpc1sxMDA1XTsKbGwgY29zdFsxMDA1XTsKCmludCBtYWluKCkKewogICAgbGwgaSxqLG4sbSx0LGEsYixjLHAsZCxlOwogICAgc2NhbmYoIiVsbGQiLCZ0KTsKICAgIGZvcihsbCBjej0xO2N6PD10O2N6KyspewogICAgICAgIHByaW50ZigiQ2FzZSAlbGxkOiAiLGN6KTsKICAgICAgICAgICAgbWVtc2V0KGNvc3QsMCxzaXplb2YoY29zdCkpOwogICAgICAgIHNjYW5mKCIlbGxkJWxsZCVsbGQiLCZuLCZtLCZwKTsKICAgICAgICBlZGdlLmNsZWFyKCk7CgogICAgICAgIGZvcihpPTE7aTw9bTtpKyspewogICAgICAgICAgICBzY2FuZigiJWxsZCVsbGQlbGxkJWxsZCIsJmEsJmIsJmQsJmUpOwogICAgICAgICAgICBjPXAqZS1kOwogICAgICAgICAgICBlZGdlLnB1c2hfYmFjayhtYWtlX3BhaXIobWFrZV9wYWlyKGEsYikgLGMpKTsKICAgICAgICB9CgogICAgICAgIGxsIGxlbj1lZGdlLnNpemUoKTsKICAgICAgICBsbCB1LHYsY2hrPTA7CiAgICAgICAgZm9yKGo9MTtqPD1uO2orKykKICAgICAgICBmb3IoaT0wO2k8bGVuO2krKyl7CiAgICAgICAgICAgICAgICB1PWVkZ2VbaV0uZmlyc3QuZmlyc3Q7CiAgICAgICAgICAgICAgICB2PWVkZ2VbaV0uZmlyc3Quc2Vjb25kOwogICAgICAgICAgICAgICAgYz1lZGdlW2ldLnNlY29uZDsKCiAgICAgICAgICAgICAgICBpZihjb3N0W3ZdPmNvc3RbdV0rYyl7CiAgICAgICAgICAgICAgICAgICAgY29zdFt2XT1jb3N0W3VdK2M7CiAgICAgICAgICAgICAgICB9CiAgICAgICAgfQoKICAgICAgICBmb3IoaT0wO2k8bGVuO2krKyl7CiAgICAgICAgICAgICAgICB1PWVkZ2VbaV0uZmlyc3QuZmlyc3Q7CiAgICAgICAgICAgICAgICB2PWVkZ2VbaV0uZmlyc3Quc2Vjb25kOwogICAgICAgICAgICAgICAgYz1lZGdlW2ldLnNlY29uZDsKCiAgICAgICAgICAgICAgICBpZihjb3N0W3ZdPmNvc3RbdV0rYyYmdmlzW3VdPT0wKXsKICAgICAgICAgICAgICAgICAgICAvL2NvdXQ8PGNvc3Rbdl08PCIgIjw8djw8ZW5kbDsKICAgICAgICAgICAgICAgICAgICBjb3N0W3ZdPWNvc3RbdV0rYzsKICAgICAgICAgICAgICAgICAgICAvL2NvdXQ8PGNvc3Rbdl08PCIgIjw8djw8ZW5kbDsKICAgICAgICAgICAgICAgIGNoaz0xOwogICAgICAgICAgICAgICAgfQogICAgICAgIH0KCiAgICAgICAgaWYoY2hrPT0xKXByaW50ZigiWUVTXG4iKTsKICAgICAgICBlbHNlIHByaW50ZigiTk9cbiIpOwogICAgfQp9

MwoKIAoKNSA4IDMKCjAgMSAxNyA4CgoxIDAgMTAgNQoKMSAyIDExIDUKCjEgNCA1IDMKCjIgMyAxMyA3CgozIDEgOSA0Cgo0IDMgMTEgMQoKMyAwIDExIDYKCiAKCjUgOCAzCgowIDEgMTcgOAoKMSAwIDEwIDUKCjEgMiAxMSA1CgoxIDQgNSAzCgoyIDMgMTMgNwoKMyAxIDkgNAoKNCAzIDExIDIKCjMgMCAxMSA2CgogCgo1IDggMgoKMCAxIDE3IDgKCjEgMCAxMCA1CgoxIDIgMTEgNQoKMSA0IDUgMwoKMiAzIDEzIDcKCjMgMSA5IDQKCjQgMyAxMSA1CgozIDAgMTEgNg==

3

 

5 8 3

0 1 17 8

1 0 10 5

1 2 11 5

1 4 5 3

2 3 13 7

3 1 9 4

4 3 11 1

3 0 11 6

 

5 8 3

0 1 17 8

1 0 10 5

1 2 11 5

1 4 5 3

2 3 13 7

3 1 9 4

4 3 11 2

3 0 11 6

 

5 8 2

0 1 17 8

1 0 10 5

1 2 11 5

1 4 5 3

2 3 13 7

3 1 9 4

4 3 11 5

3 0 11 6