1. 

/**
* FWP, Ausgewählte Probleme aus dem ACM Programming Contest
* Problem: 11874 - Travel Company
* Link: http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&category=226&problem=2985
*
*
* Method : floyd warshall
* Status : Accepted
* Runtime: 1.044
*
* @author Evgeni Pavlidis
* @version 1.0, 30/10/2010
*/

import java.io.*;
import java.util.*;

class Main
{
static StreamTokenizer st = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));

static int nextInt() throws IOException
{
st.nextToken();
return (int)st.nval;
}


public static void main(String...args) throws Exception
{
int testCases = nextInt();

int n,r,p;
int a,b, e, in;
boolean possible;

int[][] inc = new int[100][100];


for(int tc = 1; tc <= testCases; tc++)
{
possible = false;

n = nextInt();
r = nextInt();
p = nextInt();

// init
for(int i = 0; i < n; i++)
for(int j = 0; j < n; j++)
inc[i][j] = Integer.MIN_VALUE / 10;

// load roads
for(int i = 0; i < r; i++)
{
a = nextInt();
b = nextInt();
in = nextInt();
e = nextInt();

inc[a][b] = in - p * e;
}



for(int k = 0; k < n; k++)
for(int i = 0; i < n; i++)
for(int j = 0; j < n; j++)
if(k!=i && k!=j)
if(inc[i][k] + inc[k][j] > inc[i][j])
inc[i][j] = inc[i][k] + inc[k][j];


int max = Integer.MIN_VALUE;
for(int i = 0; i < n; i++)
max = Math.max(inc[i][i], max);

possible = (max > 0);

System.out.printf("Case %d: %s\n", tc, (possible? "YES":"NO"));
}
}
}