A simpler way is to add vertices in increasing order of weight and doing small to large merging with query indices stored in components. Not sure why you used edge weights.

Thanks for sharing YMSeah

I implemented the solution in JAVA using method 2.

Code :

/*
        "Everything in the universe is balanced. Every disappointment
                you face in life will be balanced by something good for you!
                        Keep going, never give up."

                        Just have Patience + 1...

*/









import java.util.*;
import java.lang.*;
import java.io.*;


public class Solution {

    static class UnionFind {
        int[] parent;
        int[] rank;

        UnionFind(int n) {
            parent = new int[n + 1];
            rank = new int[n + 1];

            for (int i = 0; i <= n; i++) {
                parent[i] = i;
                rank[i] = 0;
            }
        }

        public int find(int u) {
            if (u == parent[u]) {
                return u;
            }
            return parent[u] = find(parent[u]);
        }

        public boolean unite(int u, int v) {
            int rootU = find(u);
            int rootV = find(v);

            if (rootU == rootV) {
                return false;
            }

            if (rank[rootU] <= rank[rootV]) {
                parent[rootU] = rootV;
                rank[rootV] += rank[rootU];
            }else {
                parent[rootV] = rootU;
                rank[rootU] += rank[rootV];
            }

            return true;
        }
    }

    static class Edge implements Comparable<Edge> {
        int u;
        int v;
        int w;

        Edge (int u, int v, int w) {
            this.u = u;
            this.v = v;
            this.w = w;
        }

        public int compareTo(Edge e) {
            return Integer.compare(w, e.w);
        }
    }

    static class Pair {
        int to;
        int w;

        Pair (int to, int w) {
            this.to = to;
            this.w = w;
        }
    }

    static int MAX = 100005, DEPTH = 20;
    static List<Pair>[] graph = new List[MAX];
    static List<Pair>[] minSpanningTree = new List[MAX];
    static List<Edge> edges = new ArrayList<>();
    static int[][] ancestor = new int[MAX][DEPTH];
    static int[][] maxWeight = new int[MAX][DEPTH];
    static int[] depth = new int[MAX];
    static int[] tin = new int[MAX];
    static int[] tout = new int[MAX];
    static int n, time;

    public static void main(String[] args) throws Exception {
        out = new PrintWriter(new BufferedOutputStream(System.out));
        sc = new FastReader();

        int test = sc.nextInt();
        for (int t = 1; t <= test; t++) {
            solve(t);
        }
        out.close();
    }

    private static void solve(int t) {
        n = sc.nextInt();
        time = 0;
        int m = sc.nextInt();
        int q = sc.nextInt();
        for (int i = 0; i < n; i++) {
            graph[i] = new ArrayList<>();
            minSpanningTree[i] = new ArrayList<>();
            Arrays.fill(ancestor[i], 0);
            Arrays.fill(maxWeight[i], 0);
            tin[i] = tout[i] = depth[i] = 0;
        }
        edges.clear();
        for (int i = 0; i < m; i++) {
            int u = sc.nextInt() - 1;
            int v = sc.nextInt() - 1;
            int w = sc.nextInt();
            edges.add(new Edge(u, v, w));
            graph[u].add(new Pair(v, w));
            graph[v].add(new Pair(u, w));
        }
        kruskalMST();
        dfs(0, -1, 0);
        for (int i = 0; i < n; i++) {
            for (int j = 1; j < DEPTH; j++) {
                ancestor[i][j] = ancestor[ancestor[i][j - 1]][j - 1];
                maxWeight[i][j] = Math.max(maxWeight[i][j - 1], maxWeight[ancestor[i][j - 1]][j - 1]);
            }
        }
        for (int i = 0; i < q; i++) {
            int u = sc.nextInt() - 1;
            int v = sc.nextInt() - 1;
            out.println("from " + (u + 1) + " to " + (v + 1) + " -> " + maxWeightOnPath(u, v));
        }
    }

    private static int maxWeightOnPath(int u, int v) {
        int lcaNode = findLCA(u, v);
        int maxLeft = 0, maxRight = 0;
        for (int j = 0; j < DEPTH; j++) {
            if (isAncestor(lcaNode, ancestor[u][j])) {
                maxLeft = Math.max(maxLeft, maxWeight[u][j]);
            }
            if (isAncestor(lcaNode, ancestor[v][j])) {
                maxRight = Math.max(maxRight, maxWeight[v][j]);
            }
        }
        return Math.max(maxLeft, maxRight);
    }

    private static int findLCA(int u, int v) {
        if (depth[v] > depth[u]) {
            int temp = u;
            u = v;
            v = temp;
        }
        int diff = depth[u] - depth[v];
        u = jump(u, diff);
        if (u == v) {
            return u;
        }
        for (int i = DEPTH - 1; i >= 0; i--) {
            if (ancestor[u][i] != ancestor[v][i]) {
                u = ancestor[u][i];
                v = ancestor[v][i];
            }
        }
        return ancestor[u][0];
    }

    private static int jump(int u, int diff) {
        for (int j = DEPTH - 1; j >= 0; j--) {
            if ((diff & (1 << j)) >= 1) {
                u = ancestor[u][j];
            }
        }
        return u;
    }

    private static boolean isAncestor(int u, int v) { // u is ancestor of v
        if (u == v) {
            return true;
        }
        return tin[u] < tin[v] && tout[u] > tout[v];
    }

    private static void dfs(int currNode, int parent, int currDepth) {
        tin[currNode] = time++;
        depth[currNode] = currDepth;
        for (Pair adjacentNode : minSpanningTree[currNode]) {
            int to = adjacentNode.to;
            int w = adjacentNode.w;
            if (to == parent) {
                continue;
            }
            ancestor[to][0] = currNode;
            maxWeight[to][0] = w;
            dfs(to, currNode, currDepth + 1);
        }
        tout[currNode] = time++;
    }

    private static void kruskalMST() {
        Collections.sort(edges);
        UnionFind uf = new UnionFind(n);
        for (Edge edge : edges) {
            int u = edge.u;
            int v = edge.v;
            int w = edge.w;
            if (uf.find(u) != uf.find(v)) {
                uf.unite(u, v);
                minSpanningTree[u].add(new Pair(v, w));
                minSpanningTree[v].add(new Pair(u, w));
            }
        }
    }

    public static FastReader sc;
    public static PrintWriter out;
    static class FastReader
    {
        BufferedReader br;
        StringTokenizer str;

        public FastReader()
        {
            br = new BufferedReader(new
                    InputStreamReader(System.in));
        }

        String next()
        {
            while (str == null || !str.hasMoreElements())
            {
                try

                {
                    str = new StringTokenizer(br.readLine());
                }
                catch (IOException  lastMonthOfVacation)
                {
                    lastMonthOfVacation.printStackTrace();
                }

            }
            return str.nextToken();
        }

        int nextInt()
        {
            return Integer.parseInt(next());
        }

        long nextLong()
        {
            return Long.parseLong(next());
        }

        double nextDouble()
        {
            return Double.parseDouble(next());
        }

        String nextLine()
        {
            String str = "";
            try
            {
                str = br.readLine();
            }
            catch (IOException lastMonthOfVacation)
            {
                lastMonthOfVacation.printStackTrace();
            }
            return str;
        }
    }
}


/*
Sample Input : 

1
8
9
11
1 2 15
1 3 16
2 3 4
2 4 12
2 5 3
5 6 1
5 7 20
5 3 10
3 8 8
6 8
6 6
6 5
6 2
6 1
5 2
5 1
4 3
4 8
4 6
4 7

Sample Output : 
from 6 to 8 -> 8
from 6 to 6 -> 0
from 6 to 5 -> 1
from 6 to 2 -> 3
from 6 to 1 -> 15
from 5 to 2 -> 3
from 5 to 1 -> 15
from 4 to 3 -> 12
from 4 to 8 -> 12
from 4 to 6 -> 12
from 4 to 7 -> 20
*/