410062: GYM103934 J Apep, the Lord of Chaos

One of the main tasks of the pharaohs of the Egyptian Empire was mantaining the Maat, the order and balance, in the civilization. The great pharaoh Ramesses II did that very well. He built paths between Egypt's cities such that it were possible to travel between cities following a sequence of these paths. Therefore, for several years, the order reigned in the empire.

However, Ramesses was aware that this was not to the liking of Apep, the Lord of Chaos, a giant snake which purpose was to break Maat. In order to destroy Egypt's balance, Apep pretends to attack one path such that it would be no longer possible to travel between any pair of cities.

Every path has a strength level that depends, among other things, of the material with which it was built. Hence, the order level of Egypt is equal to the lower strength level among the paths that, if attacked, it would no longer be possible traveling between every pair of cities. If there isn't such path, we say that Egypt is in balance.

Luckily, Ramesses has a plan to prevent that Apep succeeds breaking the empire's Maat. This plan consists in adding new paths in order to raise the order level. The pharaoh wants to know the level of order after adding each of these paths and, hence, he needs your help.

The first line has to integers $$$n, m$$$ ($$$1 \leq n, m \leq 2\cdot 10^5$$$), the number of cities and paths, respectively. It's guaranteed that is possible to travel between every pair of cities using these paths.

The next $$$m$$$ lines have integers $$$v_i, u_i, w_i$$$ ($$$1 \leq v_i, u_i \leq n, 1 \leq w_i \leq 10^9$$$) describing a path with strength level $$$w_i$$$ between cities $$$v_i$$$ and $$$u_i$$$.

The next line has an integer $$$q$$$ ($$$1 \leq q \leq 2\cdot 10^5$$$), the number of paths that will be added.

The next $$$q$$$ lines have integers $$$v_i, u_i, w_i$$$ ($$$1 \leq v_i, u_i \leq n, 1 \leq w_i \leq 10^9$$$) describing an added path with strength level $$$w_i$$$ between cities $$$v_i$$$ and $$$u_i$$$. It's guraranteed that none of the paths is repeated in the input and that there isn't any path which both endpoints are the same city.

Print $$$q$$$ lines. The $$$i$$$-th line has to have the level order of Egypt after adding the first $$$i$$$ new paths or -1 if Egypt were in balance.

5 4
1 2 1
1 3 2
1 4 1
1 5 3
4
2 3 1
3 4 2
2 4 1
2 5 1

1
3
3
-1

8 9
1 2 4
2 3 7
2 6 42
3 4 21
3 5 9
3 6 11
4 5 12
6 7 41
7 8 4
7
6 5 1
2 4 2
3 8 10
7 5 2
2 8 1
1 7 10
5 1 8

4
4
4
4
4
-1
-1