#!/usr/bin/python
# another fine solution by misof

import sys

def gcd(a,b):
  if b == 0: return a
  else: return gcd(b,a%b)

class Fraction:
  def __init__ (self,num=0,denom=1):
    if denom>0: self.numerator, self.denominator = num, denom
    else: self.numerator, self.denominator = -num, -denom
    self.reduce()

  def __repr__(self): return "%s/%s" % (self.numerator, self.denominator)
  
  def reduce(self):
    neg = False
    if self.numerator<0: self.numerator, neg = -self.numerator, True
    d = gcd(self.numerator,self.denominator)
    self.numerator, self.denominator = self.numerator/d, self.denominator/d
    if neg: self.numerator = -self.numerator

  def __add__(self,rhs):
    res = Fraction()
    try: res.numerator, res.denominator = (self.numerator * rhs.denominator) + (rhs.numerator * self.denominator), self.denominator * rhs.denominator
    except: res.numerator, res.denominator = self.numerator + rhs * self.denominator, self.denominator
    res.reduce()
    return res

  def __sub__(self,rhs):
    try: neg = Fraction(-rhs.numerator, rhs.denominator)
    except: neg = -rhs
    return self + neg

  def __mul__(self,rhs):
    res = Fraction()
    try: res.numerator, res.denominator = self.numerator * rhs.numerator, self.denominator * rhs.denominator
    except: res.numerator, res.denominator = self.numerator * rhs, self.denominator
    res.reduce()
    return res

  def __radd__(self,rhs): return self + rhs
  def __rsub__(self,rhs): return self - rhs
  def __rmul__(self,rhs): return self * rhs

class Edge:
  def __init__(self,x,y,lo,hi):
    self.x, self.y, self.lo, self.hi = x, y, lo, hi

def getBoss(boss,who):
  if who==boss[who]: return who
  else: 
    boss[who] = getBoss(boss,boss[who])
    return boss[who]

def padd(poly1,poly2):
  l = max(len(poly1),len(poly2))
  res = [0]*l
  for i in range(len(poly1)): res[i] += poly1[i]
  for i in range(len(poly2)): res[i] += poly2[i]
  return res

def pmul(poly1,poly2):
  tmp = poly1
  res = [0]*(len(poly1)+len(poly2)-1)
  for i in range(len(poly1)):
    for j in range(len(poly2)):
      res[i+j] += poly1[i] * poly2[j]
  return res

def pintegrate(poly):
  res = [0] + poly
  for i in range(1,len(res)):
    res[i] *= Fraction(1,i)
  return res

def peval(poly,point):
  x = Fraction(1,1)
  res = 0
  for i in range(len(poly)):
    res += (x*poly[i])
    x *= point
  return res

def solve(N,E,minCost,maxCost):
  boss = range(N)
  for e in E:
    if e.hi <= minCost:
      xx, yy = getBoss(boss,e.x), getBoss(boss,e.y)
      if xx != yy: boss[yy] = xx

  newN = 0
  relabel = {}
  for i in range(N):
    if i==boss[i]:
      relabel[i] = newN
      newN += 1

  newE = []
  for e in E:
    if e.hi <= minCost or e.lo >= maxCost: continue
    xx, yy = getBoss(boss,e.x), getBoss(boss,e.y)
    if xx != yy: newE.append( Edge(relabel[xx],relabel[yy],e.lo,e.hi) )

  newM = len(newE)

  poly = [Fraction(0,1)]
  for choose in range(1 << newM):
    chosen = [ (choose & (1<<i)) for i in range(newM) ]

    boss = range(newN)
    for i in range(len(newE)):
      if chosen[i]:
        xx, yy = getBoss(boss,newE[i].x), getBoss(boss,newE[i].y)
        if xx != yy: boss[yy] = xx

    components=0
    for i in range(newN): 
      if boss[i]==i: components+=1

    currPoly = [ components ]
    for i in range(newM):
      if chosen[i]: factor = [ Fraction(-newE[i].lo,newE[i].hi-newE[i].lo), Fraction(1,newE[i].hi-newE[i].lo) ]
      else:         factor = [ Fraction(newE[i].hi,newE[i].hi-newE[i].lo), Fraction(-1,newE[i].hi-newE[i].lo) ]
      currPoly = pmul(currPoly,factor)
    poly = padd(poly,currPoly)
  
  poly[0] -= 1
  poly = pintegrate(poly)
  return peval(poly,maxCost) - peval(poly,minCost)


############################### main starts here #################################

T = int(sys.stdin.readline())
for test in range(T):
  C = int(sys.stdin.readline())
  if C==-1:
    print -1
    continue
  res = 0
  for comp in range(C):
    N,M = map(int,sys.stdin.readline().split(' '))
    E = []
    costmap = {}
    costmap[0] = 1
    for m in range(M):
      x,y,lo,hi = map(int,sys.stdin.readline().split(' '))
      E.append( Edge(x,y,lo,hi) )
      costmap[lo],costmap[hi] = 1,1
    costs = costmap.keys()
    costs.sort()
    for i in range(len(costs)-1): 
      res += solve(N,E,costs[i],costs[i+1])
  print res

# vim: fdm=marker