// Working program with FastReader 
import java.io.BufferedReader; 
import java.io.IOException; 
import java.io.InputStreamReader; 
import java.util.Scanner; 
import java.util.StringTokenizer; 
import java.util.*;
import java.io.*;
public class J_Road_Reform{
    public static void main(String[] args) {
       FastReader sc=new FastReader();
        PrintWriter out = new PrintWriter(System.out);
        int test = sc.nextInt();
        for(int t=0;t<test;t++){
            int n = sc.nextInt();
            int m = sc.nextInt();
            int k = sc.nextInt();
            int[] value= new int[n];
            List<Edge> greater = new ArrayList<>();
            List<Edge> smaller = new ArrayList<>();
            for(int i =0;i<m;i++){
                int a = sc.nextInt();
                int b = sc.nextInt();
                value[a-1]++;
                value[b-1]++;
                int weight = sc.nextInt();
                Edge  temp = new Edge (a,b,weight);
                if(weight>k){
                    greater.add(temp);
                }
                else{
                    smaller.add(temp);
                }
            }
            Collections.sort(greater);
            Collections.sort(smaller);
            int current = m;
            int i =greater.size()-1;
            int j =0;
            boolean atleastOne = false;
            long ans = 0;
            int smallerAns = 0;
            boolean visitedSmaller = false;
            outer:while(current>(n-1)){
                if(i>0){
                    int one = greater.get(i).a-1;
                    int two = greater.get(i).b-1;
                    if(value[one]>1 && value[two]>1){
                        i--;
                        current--;
                    }
                    else{
                        ans += greater.get(i).weight-k;
                        atleastOne = true;
                        i--;
                    }
                }
                else if(i==0){
                    int one = greater.get(i).a-1;
                    int two = greater.get(i).b-1;
                    if(value[one]>1 && value[two]>1){
                    }
                    else{
                        ans += greater.get(i).weight-k;
                        i--;
                        atleastOne = true;
                    }
                    if(atleastOne){
                        break outer;
                    }
                    else{
                        ans += greater.get(i).weight-k;
                        i--;
                    }
                }
                else{
                    if(j<smaller.size()){
                        visitedSmaller = true;
                        int three = smaller.get(j).b-1;
                        int four = smaller.get(j).b-1;
                        if(value[three]>1 && value[four]>1){
                            j++;
                            current--;
                        }
                        else{
                            smallerAns = Math.max(smallerAns,smaller.get(j).weight);
                            j++;
                        }
                    }
                    else{
                        ans=0;
                        current--;
                    }
                }
            }
            while(i>=0){
                ans += greater.get(i).weight-k;
                i--;
            }
            while(j<smaller.size()){
                smallerAns = Math.max(smallerAns,smaller.get(j).weight);
                j++;
            }
            if(visitedSmaller){
                if(ans==0){
                    ans = k-smallerAns;
                }
                else{
                    ans = Math.min(ans,k-smallerAns);
                }
            }
            out.println(ans);
        }
        out.close();
    }
    public static class Edge implements Comparable<Edge>{
        int a;
        int b;
        int weight;
        public Edge(int a,int b,int weight){
            this.a = a;
            this.b = b;
            this.weight = weight;
        }
        @Override
        public int compareTo(Edge node) {
            return Integer.compare(this.weight, node.weight);
        }

    }
    
    public static class FastReader 
    { 
        BufferedReader br; 
        StringTokenizer st; 

        public FastReader() 
        { 
            br = new BufferedReader(new
                    InputStreamReader(System.in)); 
        } 

        String next() 
        { 
            while (st == null || !st.hasMoreElements()) 
            { 
                try
                { 
                    st = new StringTokenizer(br.readLine()); 
                } 
                catch (IOException e) 
                { 
                    e.printStackTrace(); 
                } 
            } 
            return st.nextToken(); 
        } 

        int nextInt() 
        { 
            return Integer.parseInt(next()); 
        } 

        long nextLong() 
        { 
            return Long.parseLong(next()); 
        } 

        double nextDouble() 
        { 
            return Double.parseDouble(next()); 
        } 

        String nextLine() 
        { 
            String str = ""; 
            try
            { 
                str = br.readLine(); 
            } 
            catch (IOException e) 
            { 
                e.printStackTrace(); 
            } 
            return str; 
        } 
}
}
