Untitled

#include<bits/stdc++.h>
using namespace std;

const int N = 305;
const int inf = 1e9;

int n, m, q;
map<int, pair<int, int>> ID;
vector<bool> hasEdge[N];
vector<pair<int, int>> a[N];
int dist[N][15];
bool vis[N][15];

void init(){
  cin >> n >> m;
  ID.clear();
  for (int i = 0; i < n; i++) a[i].clear(), hasEdge[i].clear();
  for (int i = 0; i < m; i++){
    int id, u, v, w;
    cin >> id >> u >> v >> w;
    a[u].push_back({v, w});
    hasEdge[u].push_back(1);
    int sz = hasEdge[u].size();
    ID[id] = {u, sz - 1};
  }
}

int dfs(int st, int ed, int M){
  for (int i = 0; i < n; i++){
    for (int j = 0; j <= M; j++){
      dist[i][j] = inf;
      vis[i][j] = false;
    }
  }
  priority_queue<pair<int, pair<int, int>>, vector<pair<int, pair<int, int>>>, greater<pair<int, pair<int, int>>>> q;
  q.push({0, {st, 0}});
  dist[st][0] = 0;
  int ans = inf;
  while(q.size()){
    auto U = q.top(); q.pop();
    int cost = U.first;
    int u = U.second.first;
    int cntVoucher = U.second.second;
    if (vis[u][cntVoucher]) continue;
    if (u == ed) ans = min(ans, inf);
    vis[u][cntVoucher] = true;
    int sz = hasEdge[u].size();
    for (int i = 0; i < sz; i++){
      if (!hasEdge[u][i]) continue;
      int v = a[u][i].first;
      int w = a[u][i].second;
      if (cost + w < dist[v][cntVoucher]){
        dist[v][cntVoucher] = cost + w;
        q.push({dist[v][cntVoucher], {v, cntVoucher}});
      }
      if (cntVoucher < M && cost + w / 2 < dist[v][cntVoucher + 1]){
        dist[v][cntVoucher + 1] =cost + w / 2;
        q.push({dist[v][cntVoucher + 1], {v, cntVoucher + 1}});
      }
    }
  }
  if (ans == inf) ans = -1;
  return ans;
}

void add(int id, int u, int v, int w){
    a[u].push_back({v, w});
    hasEdge[u].push_back(1);
    int sz = hasEdge[u].size();
    ID[id] = {u, sz - 1};
}

void remove(int id){
  auto u = ID[id];
  hasEdge[u.first][u.second] = 0;
}


void solve(){
  // nhập số truy vấn
  cin >> q;
  // nhập n số đỉnh, m số đường đi
  // mỗi đường đi có dạng id, u, v, cost, đi từ u đến v với chi phi cost
  init();
  while(q--){
    int type; cin >> type;
    // loại 1 là add, id, u, v, cost
    if (type == 1){
      int id, u, v, w; cin >> id >> u >> v >> w;
      add(id, u, v, w);
    }
    // xóa đường đi có id
    if (type == 2){
      int id; cin >> id;
      remove(id);
    }
    // tìm min từ u -> v với M voucher
    if (type == 3){
      int u, v, M; cin >> u >> v >> M;
      cout << "Cost: " << dfs(u, v, M) << '\n';
    }
  }
}

int32_t main() {
  ios_base::sync_with_stdio(false), cin.tie(0);
  int t;
  // nhập số lượng 
  cin >> t;
  while(t--) solve();
}