CF603E.Pastoral Oddities

In the land of Bovinia there are n pastures, but no paths connecting the pastures. Of course, this is a terrible situation, so Kevin Sun is planning to rectify it by constructing m undirected paths connecting pairs of distinct pastures. To make transportation more efficient, he also plans to pave some of these new paths.

Kevin is very particular about certain aspects of path-paving. Since he loves odd numbers, he wants each pasture to have an odd number of paved paths connected to it. Thus we call a paving sunny if each pasture is incident to an odd number of paved paths. He also enjoys short paths more than long paths, so he would like the longest paved path to be as short as possible. After adding each path, Kevin wants to know if a sunny paving exists for the paths of Bovinia, and if at least one does, the minimum possible length of the longest path in such a paving. Note that "longest path" here means maximum-weight edge.

在牛尼亚（Bovinia）境内有 $n$ 片牧场，但这些牧场之间尚无任何路径相连。显然，这是一个极其糟糕的局面，因此凯文·孙（Kevin Sun）计划通过修建 $m$ 条无向路径来连接若干对互异的牧场，以改善现状。为了提升运输效率，他还计划对其中一部分新建路径进行铺装。

凯文对路径铺装有着非常特别的要求。由于他钟爱奇数，他希望每片牧场所连的已铺装路径数量均为奇数。因此，我们将满足“每片牧场均与奇数条已铺装路径关联”的铺装方案称为阳光铺装（sunny paving）。此外，他更偏爱短路径而非长路径，因此他希望所铺装路径中最长路径的长度尽可能小。在每次添加一条新路径后，凯文都希望知道：当前牛尼亚的所有路径中是否存在阳光铺装；若存在至少一种，则该铺装方案中最长铺装路径的最小可能长度是多少？ 注意：此处“最长路径”指的是权重最大的边。

The first line contains two integers n (2 ≤ n ≤ 100 000) and m (1 ≤ m ≤ 300 000), denoting the number of pastures and paths, respectively. The next m lines each contain three integers a__i, b__i and l__i, describing the i-th path. The i-th path connects pastures a__i and b__i (1 ≤ a__i, b__i ≤ n; a__i ≠ b__i) and has length l__i (1 ≤ l__i ≤ 109). Paths are given in the order in which they are constructed.

第一行包含两个整数 $n$（$2 \leq n \leq 100\,000$）和 $m$（$1 \leq m \leq 300\,000$），分别表示牧场的数量和路径的数量。接下来的 $m$ 行每行包含三个整数 $a_i$、$b_i$ 和 $l_i$，描述第 $i$ 条路径。第 $i$ 条路径连接牧场 $a_i$ 和 $b_i$（$1 \leq a_i,\, b_i \leq n$；$a_i \neq b_i$），其长度为 $l_i$（$1 \leq l_i \leq 10^9$）。路径按其建造顺序给出。

Output m lines. The i-th line should contain a single integer denoting the minimum possible length of the longest path (maximum-weight edge) in a sunny paving using only the first i paths. If Kevin cannot pave a set of paths so that each pasture is incident to an odd number of paved paths, output  - 1.

Note that the paving is only hypothetical—your answer after adding the i-th path should not be affected by any of your previous answers.

输出 m 行。第 i 行应包含一个整数，表示仅使用前 i 条路径构造“晴朗铺路”（sunny paving）时，最长路径（即最大权重边）的最小可能长度。若凯文无法铺设一组路径，使得每个牧场均与奇数条已铺设路径关联，则输出 -1。

注意：该铺路仅为假设性构造——在加入第 i 条路径后所得答案，不应受此前任意一次答案的影响。

For the first sample, these are the paths that Kevin should pave after building the i-th path:

1. No set of paths works.
2. Paths 1 (length 4) and 2 (length 8).
3. Paths 1 (length 4) and 2 (length 8).
4. Paths 3 (length 2) and 4 (length 3).

In the second sample, there never exists a paving that makes Kevin happy.

对于第一个样例，凯文在修建第 $i$ 条路径后应铺设的路径如下：

1. 不存在满足条件的路径集合。
2. 路径 1（长度为 4）和路径 2（长度为 8）。
3. 路径 1（长度为 4）和路径 2（长度为 8）。
4. 路径 3（长度为 2）和路径 4（长度为 3）。

在第二个样例中，始终不存在能使凯文满意的铺设方案。