import java.util.*;
import java.io.*;
public class Main
{
	public static void main(String[] args)throws Exception
	{
	    BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
	    PrintWriter pw=new PrintWriter(System.out);
	    int t=Integer.parseInt(br.readLine());
	    while(t-->0)
	    {
	        String s[]=(br.readLine()).split(" ");
	        int n=Integer.parseInt(s[0]);
	        int m=Integer.parseInt(s[1]);
	        int k=Integer.parseInt(s[2]);
	        LinkedList<Integer> ll[]=new LinkedList[n+1];//parents
	        PriorityQueue<Integer> pq[]=new PriorityQueue[n+1];//difference
	        LinkedList<data> ar[]=new LinkedList[n+1];//graph goes here 
	        for(int i=0;i<=n;i++)
	        {
	            ll[i]=new LinkedList<Integer>();
	        }
	        for(int i=0;i<=n;i++)
	        {
	            pq[i]=new PriorityQueue<Integer>();
	        }
	        for(int i=0;i<=n;i++)
	        {
	            ar[i]=new LinkedList<data>();
	        }
	        
	        
	        boolean vis[]=new boolean[n+1];
	        boolean par_vis[]=new boolean[n+1];
	        
	        for(int i=1;i<=m;i++)
	        {
	            String s1[]=(br.readLine()).split(" ");
	            int x=Integer.parseInt(s1[0]);
	            int y=Integer.parseInt(s1[1]);
	            int speed=Integer.parseInt(s1[2]);
	            data d1=new data(y,speed);
	            data d2=new data(x,speed);
	            ar[x].add(d1);
	            ar[y].add(d2);
	        }
	        
	        //bfs
	        LinkedList<data> q=new LinkedList<data>();
	        data x=new data(1,0);
	        q.add(x);
	        vis[1]=true;
	        while(q.size()!=0)
	        {
	            int num=(q.poll()).node;
	            par_vis[num]=true;
	            Iterator<data> it=ar[num].iterator();
	            while(it.hasNext())
	            {
	                data node2=it.next();
	                int num2=node2.node;
	                int dist2=node2.wt;
	                if(!vis[num2])
	                {
	                    q.add(node2);
	                    vis[num2]=true;
	                }
	                if(!par_vis[num2])
	                {
	                    ll[num2].add(num);
	                    int diff=k-dist2;
	                    if(diff<0)
	                    {
	                        diff*=-1;
	                    }
	                    pq[num2].add(diff);
	                }
	                
	            }
	            
	        }
	        int min=Integer.MAX_VALUE;
	        int sum=0;
	        for(int i=2;i<=n;i++)
	        {
	            min=Math.min(min,(pq[i].peek()));
	            
	        }
	        
	        pw.println(min);
	        
	        
	    }
	    pw.flush();
	    
	    
	}
}
class data
{
    int node;
    int wt;
    public data(int node,int wt)
    {
        this.node=node;
        this.wt=wt;
    }
}
