class PrioQueue:
    def __init__(self, elist=None):
        if elist is None:
            elist = []
        self._elems = list(elist)
        if elist:
            self.buildheap()

    def is_empty(self):
        return not self._elems

    def peek(self):
        if self.is_empty():
            raise ValueError("in peek")
        return self._elems[0]

    def enqueue(self, e):
        self._elems.append(e)
        self.siftup(e, len(self._elems) - 1)

    def siftup(self, e, last):
        elem, i, j = self._elems, last, (last - 1) // 2
        while j >= 0 and elem[i] < elem[j]:
            elem[i], elem[j] = elem[j], elem[i]
            i, j = j, (j - 1) // 2

    def dequeue(self):
        if self.is_empty():
            raise ValueError("in dequeue")
        e0 = self._elems[0]
        e = self._elems.pop()
        if len(self._elems) > 0:
            self.siftdown(e, len(self._elems) - 1)
        return e0

    def siftdown(self, e, end):
        elem, i, j = self._elems, 0, 1
        while j <= end:
            if j + 1 <= end and elem[j + 1] < elem[j]:
                j += 1
            if e <= elem[j]:
                break
            elem[i] = elem[j]
            i, j = j, j * 2 + 1
        elem[i] = e

    def buildheap(self):
        end = len(self._elems)
        for i in range(end // 2, -1, -1):
            self.siftdown(self._elems[i], -1)


def sol(lst, n, k):
    min = lst[0]
    count = 2
    ans = 0
    mlst = [0] * (n + 1)
    dic = {lst[0][1]: [(lst[0][2], lst[0][0])], lst[0][2]: [(lst[0][1], lst[0][0])]}
    for i in range(1, len(lst)):
        r = lst[i]
        if abs(r[0] - k) < abs(min[0] - k):
            min = r
        try:
            dic[r[1]].append((r[2], r[0]))
        except:
            dic[r[1]] = [(r[2], r[0])]
        try:
            dic[r[2]].append((r[1], r[0]))
        except:
            dic[r[2]] = [(r[1], r[0])]

    pq = PrioQueue()
    for y, wn in dic[min[1]]:
        if y != min[2]:
            pq.enqueue((wn, min[1], y))
    for y, wn in dic[min[2]]:
        if y != min[1]:
            pq.enqueue((wn, min[2], y))
    mlst[min[1]] = mlst[min[2]] = 1

    while count < n:
        w, x1, x2 = pq.dequeue()
        if mlst[x2]:
            continue
        count += 1
        mlst[x2] = 1
        if w > k:
            ans += (w-k)
        cb = dic[x2]
        for y, wn in cb:
            if not mlst[y]:
                pq.enqueue((wn, x2, y))
    if ans > 0 and min[0] <= k:
        print(ans)
    else:
        print(ans + abs(min[0] - k))



t = int(input())
for qwq in range(t):
    abk = input().split()
    lst = []
    for qw in range(int(abk[1])):
        rt = input().split()
        r = [int(rt[i]) for i in range(2, -1, -1)]
        lst.append(r)
    sol(lst, int(abk[0]), int(abk[2]))
