There are n cities and m bidirectional roads in Berland. The i-th road connects the cities x_i and y_i, and has the speed limit s_i. The road network allows everyone to get from any city to any other city. 

The Berland Transport Ministry is planning a road reform.

First of all, maintaining all m roads is too costly, so m - (n - 1) roads will be demolished in such a way that the remaining (n - 1) roads still allow to get to any city from any other city. Formally, the remaining roads should represent an undirected tree.

Secondly, the speed limits on the remaining roads might be changed. The changes will be done sequentially, each change is either increasing the speed limit on some road by 1, or decreasing it by 1. Since changing the speed limit requires a lot of work, the Ministry wants to minimize the number of changes.

The goal of the Ministry is to have a road network of (n - 1) roads with the maximum speed limit over all roads equal to exactly k. They assigned you the task of calculating the minimum number of speed limit changes they have to perform so the road network meets their requirements.

For example, suppose the initial map of Berland looks like that, and k = 7:

<image>

Then one of the optimal courses of action is to demolish the roads 1–4 and 3–4, and then decrease the speed limit on the road 2–3 by 1, so the resulting road network looks like that:

<image>

Input

The first line contains one integer t (1 ≤ t ≤ 1000) — the number of test cases.

The first line of each test case contains three integers n, m and k (2 ≤ n ≤ 2 ⋅ 10^5; n - 1 ≤ m ≤ min(2 ⋅ 10^5, (n(n-1))/(2)); 1 ≤ k ≤ 10^9) — the number of cities, the number of roads and the required maximum speed limit, respectively.

Then m lines follow. The i-th line contains three integers x_i, y_i and s_i (1 ≤ x_i, y_i ≤ n; x_i ≠ y_i; 1 ≤ s_i ≤ 10^9) — the cities connected by the i-th road and the speed limit on it, respectively. All roads are bidirectional.

The road network in each test case is connected (that is, it is possible to reach any city from any other city by traveling along the road), and each pair of cities is connected by at most one road.

The sum of n over all test cases does not exceed 2 ⋅ 10^5. Similarly, the sum of m over all test cases does not exceed 2 ⋅ 10^5.

Output

For each test case, print one integer — the minimum number of changes the Ministry has to perform so that the maximum speed limit among the remaining (n - 1) roads is exactly k.

Example

Input


4
4 5 7
4 1 3
1 2 5
2 3 8
2 4 1
3 4 4
4 6 5
1 2 1
1 3 1
1 4 2
2 4 1
4 3 1
3 2 1
3 2 10
1 2 8
1 3 10
5 5 15
1 2 17
3 1 15
2 3 10
1 4 14
2 5 8


Output


1
3
0
0

Note

The explanation for the example test:

The first test case is described in the problem statement.

In the second test case, the road network initially looks like that:

<image>

The Ministry can demolish the roads 1–2, 3–2 and 3–4, and then increase the speed limit on the road 1–4 three times.

In the third test case, the road network already meets all the requirements.

In the fourth test case, it is enough to demolish the road 1–2 so the resulting road network meets the requirements.
import java.util.*;
import java.io.*;
public class Solution implements Runnable {
    FastScanner sc;
    PrintWriter pw;
    
    final class FastScanner {
        BufferedReader br;
        StringTokenizer st;
 
        public FastScanner() {
            try {
                br = new BufferedReader(new InputStreamReader(System.in));
                st = new StringTokenizer(br.readLine());
            } catch (Exception e) {
                e.printStackTrace();
            }
        }
 
        public long nlo() {
            return Long.parseLong(next());
        }
 
        public String next() {
            if (st.hasMoreTokens()) return st.nextToken();
            try {
                st = new StringTokenizer(br.readLine());
            } catch (Exception e) {
                e.printStackTrace();
            }
            return st.nextToken();
        }
 
        public int ni() {
            return Integer.parseInt(next());
        }
 
        public String nli() {
            String line = "";
            if (st.hasMoreTokens()) line = st.nextToken();
            else try {
                return br.readLine();
            } catch (IOException e) {
                e.printStackTrace();
            }
            while (st.hasMoreTokens()) line += " " + st.nextToken();
            return line;
        }
 
        public double nd() {
            return Double.parseDouble(next());
        }
    }
    public static void main(String[] args) throws Exception
    {
        new Thread(null,new Solution(),"codeforces",1<<28).start();
    }
    public void run()
    {
        sc=new FastScanner();
        pw=new PrintWriter(System.out);
        try{
        solve();}
        catch(Exception e)
        {
            pw.println(e);
        }
        pw.flush();
        pw.close();
    }
    public long gcd(long a,long b)
    {
        return b==0L?a:gcd(b,a%b);
    }
    public long ppow(long a,long b,long mod)
    {
        if(b==0L)
        return 1L;
        long tmp=1;
        while(b>1L)
        {
            if((b&1L)==1L)
            tmp*=a;
            a*=a;
            a%=mod;
            tmp%=mod;
            b>>=1;
        }
        return (tmp*a)%mod;
    }
    public long pow(long a,long b)
    {
        if(b==0L)
        return 1L;
        long tmp=1;
        while(b>1L)
        {
            if((b&1L)==1)
            tmp*=a;
            a*=a;
            b>>=1;
        }
        return (tmp*a);
    }
    public  int gcd(int x,int y)
    {
        return y==0?x:gcd(y,x%y);
    }
   
    //////////////////////////////////
    /////////////  LOGIC  ///////////
    ////////////////////////////////
    public int[] parent,sz;
    public void solve() throws Exception{
        int t=sc.ni();
        while(t-->0){
            int n=sc.ni();
            int m=sc.ni();
            int k=sc.ni();
            sz=new int[n];
            parent=new int[n];
            for(int i=0;i<n;i++)
            parent[i]=i;
            int[][] edges=new int[m][3];
            int close=0,min=Integer.MAX_VALUE;
            for(int i=0;i<m;i++){
                edges[i][0]=sc.ni()-1;
                edges[i][1]=sc.ni()-1;
                edges[i][2]=sc.ni();
                if(Math.abs(edges[i][2]-k)<min){
                    min=Math.abs(edges[i][2]-k);
                    close=edges[i][2];
                }
            }
            Arrays.sort(edges,new Comparator<int[]>(){
                public int compare(int[] arr,int[] brr){
                    return arr[2]-brr[2];
                }
            });
            long max=0,ans=0;
            for(int[] arr:edges){
                boolean res=union(arr[0],arr[1]);
                if(res&&arr[2]>k)
                    ans+=Math.abs(k-arr[2]);
                if(res)
                    max=Math.max(max,arr[2]);
            }
            if(max<close)
            ans=min;
            else if(max<k)
            ans=k-max;
            pw.println(ans);

        }
    }
    public boolean union(int x,int y){
        int p1=find_parent(x);
        int p2=find_parent(y);
        if(p1==p2)
        return false;
        if(sz[p1]<sz[p2]){
            parent[p1]=p2;
            sz[p2]=Math.max(sz[p2],1+sz[p1]);
        }
        else{
            parent[p2]=p1;
            sz[p1]=Math.max(sz[p1],1+sz[p2]);
        }
        return true;
    }
    public int find_parent(int p){
        while(parent[p]!=p){
            p=find_parent(parent[p]);
        }
        return p;
    }
}