We can answer the queries offline:
Sort edges by cost.
Build DSU (Disjoint Set Union) over vertices of a graph.
Add edges one by one and each time we union two separeate sets we can answer subset of queries such that s[i] in one of the set and t[i] is in the other. The answer is the cost of current edge.
To understand that this situation happens and answer queries you can use hashtables for each of subsets.
Initially each vertex in his own subset. And each subset has it's own hashtable. Add query i into two hashtables: one for t[i] and one for s[i]. When we join two subsets we have to add all queries from the smaller hashtable into the larger one. All queries contained by both hashtables can be answered right now. Complexity of this merging will be Q log Q because we merge smaller table into the larger one.
**PS:** You can use std::set in C++ but the total complexity will be Q (log Q)^2

Also there is an online algorithm with (N log N + M log M) graph preprocessing:
1) build a minimal spanning tree
2) select any vertex as root.
3) during the dfs remember for each vertex i it's p[i][0] — parent, p[i][1] — second parent, p[i][2] 4-th parent .. p[i][k] — 2^k th parent. Along with the parents can store w[i][k] — maximal weight of the edges between vertex i and it's 2^k th parent. Also for each vertex we have to remember it's distance from the root.
4) to process a query (x, y) you have to find z = LCA(x, y) (Least Common Ancestor) using above information about parents in O(log(n)). At the same time you can find maximal weight between z and y, and between z and y