#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");
    }
}