/VOI 14 Bài 3 - Mạng truyền thông

              #include <iostream>
        using namespace std;
        
        #define SIZE 100000 + 5
        
        int root[SIZE];
        
        void reload(int n) {
          for (int i = 1; i <= n; i++) root[i] = i;
        }
        
        int find(int u) {
          if (root[u] != u) root[u] = find(root[u]);
          return root[u];
        }
        
        int connect(int u, int v) {
          int rootU = find(u);
          int rootV = find(v);
        
          if (rootU == rootV) return 0;
          root[rootV] = rootU;
          return 1;
        }
        
        
        struct Edge {
          int u, v, t;
        };
        
        int main() {
          int t;
          cin >> t;
        
          while (t--) {
            int n, m;
            cin >> n >> m;
        
            reload(n);
        
            int* arr = new int[n + 1]{ 0 };
            int* brr = new int[n + 1]{ 0 };
        
            for (int i = 1; i <= n - 1; i++) cin >> arr[i];
            for (int i = 1; i <= n - 1; i++) cin >> brr[i];
        
            Edge* e = new Edge[m + 1];
        
            for (int i = 1; i <= m; i++) cin >> e[i].u >> e[i].v >> e[i].t;
        
            int A = 0;
            int B = 0;
        
            for (int i = 1; i <= m; i++) {
              if (e[i].t == 1) {
                A += connect(e[i].u, e[i].v);
              }
            }
        
            reload(n);
        
            for (int i = 1; i <= m; i++) {
              if (e[i].t == 2) {
                B += connect(e[i].u, e[i].v);
              }
            }
            //cout << A << " " << B << endl;
            int money = 2 * 1000000000 + 1;
        
            int x, y;
            
            for (int i = max(0, n - 1 - B); i <= min(A, n - 1); i++) {
              if (money > arr[i] + brr[n - 1 - i]) {
                money = arr[i] + brr[n - 1 - i];
                x = i;
                y = n - 1 - x;
              }
            }
        
        
            int* mark = new int[m + 1]{ 0 };
        
            for (int i = 1; i <= m; i++) {
              if (e[i].t == 1) {
                mark[i] = connect(e[i].u, e[i].v);
              }
            }
        
            reload(n);
        
            int cnt = 0;
        
            for (int i = 1; i <= m; i++) {
              if (mark[i] == 1) {
                cnt += connect(e[i].u, e[i].v);
              }
            }
            
            for (int i = 1; i <= m && cnt < x; i++) {
              if (e[i].t == 1 && !mark[i]) {
                mark[i] = connect(e[i].u, e[i].v);
                cnt += mark[i];
              }
            }
            
            for (int i = 1; i <= m; i++) {
              if (e[i].t == 2) {
                mark[i] = connect(e[i].u, e[i].v);
              }
            }
        
            for (int i = 1; i <= m; i++) {
              if (mark[i] == 1) cout << i << " ";
            }
        
            cout << endl;
          }
          
          return 0;
        }