Description

有n个变量w[1]~w[n]，每个变量可以取W或-W。

有p个式子，形如$H_i=a_i|w[x_i]-w[y_i]|+b_i|w[y_i]-w[z_i]|+c_i|w[z_i]-w[xi]| +d_i(w[x_i]-w[y_i])+e_i(w[y_i]-w[z_i])+f_i(w[z_i]-w[x_i])$。 有q个条件，形如w[x]<=w[y]或w[x]=w[y]或w[x]<w[y]。 最小化sigma(wi)+sigma(Hi)。

Input Format

第一行一个整数t表示数据组数。 每组数据第一行四个整数n,W,p,q表示节点数。 接下来p行每行九个整数xi,yi,zi,ai,bi,ci,di,ei,fi。 接下来q行每行三个整数x,y,r。 r=0表示w[x]<=w[y]；r=1表示w[x]=w[y]；r=2表示w[x]<w[y]。 保证存在方案。 t<=10，n<=500，p,q<=1000，1<=W<=10^6， 0<=ai,bi,ci,di,ei,fi<=1000。

Output Format

每组数据输出一行一个整数表示sigma(wi)+sigma(Hi)的最小值。

1
3 1 1 1
1 2 3 1 1 1 1 1 1 
1 2 2

3