#include <bits/stdc++.h>
using namespace std;
class Edge {
 public:
  int src, dest, weight;
};
class Graph {
 public:
  int V, E;
  Edge* edges;
  list<int>* adj;
  Graph(int v, int e);
  void addEdge(int v, int u);
  void BFS(int s);
  void DFS(int s);
  void dfs(int v, int vis[]);
};
Graph::Graph(int v, int e) {
  this->V = v;
  this->E = e;
  this->edges = new Edge[sizeof(Edge) * e];
  this->adj = new list<int>[v];
}
Graph* createGraph(int V, int E) {
  Graph* graph = new Graph(V, E);
  graph->E = E;
  graph->V = V;
  graph->edges = new Edge[sizeof(Edge) * E];
  graph->adj = new list<int>[V];
  return graph;
}
void Graph::addEdge(int v, int u) { adj[v].push_back(u); }
void Graph::BFS(int s) {
  int* vis = new int[V];
  memset(vis, -1, sizeof(vis));
  queue<int> q;
  q.push(s);
  vis[s] = 1;
  while (!q.empty()) {
    s = q.front();
    cout << s << " ";
    q.pop();
    for (auto i = adj[s].begin(); i != adj[s].end(); i++) {
      if (vis[*i] != 1) {
        vis[*i] = 1;
        q.push(*i);
      }
    }
  }
}
void Graph::dfs(int v, int vis[]) {
  cout << v << " ";
  vis[v] = 1;
  for (auto i = adj[v].begin(); i != adj[v].end(); i++) {
    if (vis[*i] != 1) {
      dfs(*i, vis);
    }
  }
}
void Graph::DFS(int s) {
  int* vis = new int[V];
  memset(vis, 0, sizeof(vis));
  dfs(s, vis);
}
int find(int parent[], int i) {
  if (parent[i] == i) {
    return i;
  }
  return find(parent, parent[i]);
}
void Union(int parent[], int rank[], int x, int y) {
  if (rank[x] < rank[y]) {
    parent[x] = y;
  } else if (rank[x] > rank[y]) {
    parent[y] = x;
  } else {
    parent[y] = x;
    rank[x]++;
  }
}
int isCycle(Graph* graph) {
  int* parent = new int[graph->V * sizeof(int)];
  int* rank = new int[graph->V * sizeof(int)];
  memset(rank, 0, sizeof(int) * graph->V);
  int c = 0;
  for (int i = 0; i < graph->V; i++) {
    parent[i] = i;
  }
  for (int i = 0; i < graph->E; i++) {
    int x = find(parent, graph->edges[i].src);
    int y = find(parent, graph->edges[i].dest);
    if (x == y) {
      return 1;
    } else {
      Union(parent, rank, x, y);
    }
  }
  return 0;
}
int myComp(const void* a, const void* b) {
  Edge* a1 = (Edge*)a;
  Edge* b1 = (Edge*)b;
  return a1->weight > b1->weight;
}
long long KrushukalMst(Graph* graph) {
  int V = graph->V;
  Edge result[V];
  int e = 0;
  int i = 0;
  qsort(graph->edges, graph->E, sizeof(graph->edges[0]), myComp);
  int* parent = new int[graph->V * sizeof(int)];
  int* rank = new int[graph->V * sizeof(int)];
  for (int j = 0; j < V; j++) {
    parent[j] = j;
    rank[j] = 0;
  }
  while (e < V - 1 && i < graph->E) {
    Edge next_edge = graph->edges[i++];
    int x = find(parent, next_edge.src);
    int y = find(parent, next_edge.dest);
    if (x != y) {
      result[e++] = next_edge;
      Union(parent, rank, x, y);
    }
  }
  long long mcost = 0;
  for (int i = 0; i < e; i++) {
    cout << result[i].src << " " << result[i].dest << " " << result[i].weight
         << endl;
    mcost += result[i].weight;
  }
  cout << mcost << endl;
  return mcost;
}
int main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  int t;
  cin >> t;
  while (t--) {
    int V, E, k;
    cin >> V >> E >> k;
    Graph* graph = new Graph(V, E);
    int nd = E - (V - 1);
    vector<int> v;
    for (int i = 0; i < E; i++) {
      int src, des, weight = 0;
      cin >> src >> des >> weight;
      v.push_back(weight);
      graph->edges[i].src = src;
      graph->edges[i].dest = des;
      graph->edges[i].weight = weight;
    }
    sort(v.rbegin(), v.rend());
    int i = 0;
    int c = 0;
    int mm;
    while (i < v.size() && v[i] > k) {
      c++;
      i++;
      if (c == nd) {
        break;
      }
      mm = v[i - 1];
    }
    int ans = 0;
    if (v[i] > k) {
      for (i; i < v.size(); i++) {
        if (v[i] >= k) {
          ans += (v[i] - k);
        }
      }
    } else {
      ans = min(abs(v[i] - k), abs(mm - k));
    }
    cout << ans << endl;
  }
  return 0;
}
