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.

Input

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 ai, bi and li, describing the i-th path. The i-th path connects pastures ai and bi (1 ≤ ai, bi ≤ n; ai ≠ bi) and has length li (1 ≤ li ≤ 109). Paths are given in the order in which they are constructed. 

Output

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.

Examples

Input

4 4
1 3 4
2 4 8
1 2 2
3 4 3


Output

-1
8
8
3


Input

3 2
1 2 3
2 3 4


Output

-1
-1


Input

4 10
2 1 987
3 2 829
4 1 768
4 2 608
3 4 593
3 2 488
4 2 334
2 1 204
1 3 114
1 4 39


Output

-1
-1
829
829
768
768
768
488
334
204

Note

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.
import java.io.OutputStream;
import java.io.IOException;
import java.io.InputStream;
import java.io.PrintWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.TreeSet;
import java.util.ArrayList;
import java.util.List;
import java.util.StringTokenizer;
import java.io.BufferedReader;
import java.io.InputStream;

/**
 * Built using CHelper plug-in
 * Actual solution is at the top
 *
 * @author AlexFetisov
 */
public class Main {
    public static void main(String[] args) {
        InputStream inputStream = System.in;
        OutputStream outputStream = System.out;
        InputReader in = new InputReader(inputStream);
        PrintWriter out = new PrintWriter(outputStream);
        TaskE_Pastushka_LinkCutTree solver = new TaskE_Pastushka_LinkCutTree();
        solver.solve(1, in, out);
        out.close();
    }

    static class TaskE_Pastushka_LinkCutTree {
        private List<Edge> edges;
        private TreeSet<Edge> dict;
        Node[] vertexNodes;
        List<Node> edgesNodes;

        public void solve(int testNumber, InputReader in, PrintWriter out) {
            int n = in.nextInt();
            int countEdges = in.nextInt();
            int countOddComponents = n;
            prepareLinkCutTree(n);
            edges = new ArrayList<Edge>();
            dict = new TreeSet<Edge>();

            for (int i = 0; i < countEdges; ++i) {
                int a = in.nextInt() - 1;
                int b = in.nextInt() - 1;
                int cost = in.nextInt();
//            System.err.println(a + " " + b + " " + cost);

                if (TaskE_Pastushka_LinkCutTree.LinkCutTree.isConnected(vertexNodes[a], vertexNodes[b])) {
                    Node maxEdgeOnPath = TaskE_Pastushka_LinkCutTree.LinkCutTree.pathMax(vertexNodes[a], vertexNodes[b]);
                    if (cost < edges.get(maxEdgeOnPath.id).cost) {
                        dict.remove(edges.get(maxEdgeOnPath.id));
                        cut(maxEdgeOnPath.id);
                        addEdge(a, b, cost);
                    }
                } else {
//                System.err.println("NOT CONNECTED");
                    int sizeA = TaskE_Pastushka_LinkCutTree.LinkCutTree.size(vertexNodes[a]);
                    int sizeB = TaskE_Pastushka_LinkCutTree.LinkCutTree.size(vertexNodes[b]);
//                System.err.println("SIZES: " + sizeA + ", " + sizeB);
                    if (sizeA % 2 == 1 && sizeB % 2 == 1) {
                        countOddComponents -= 2;
                    }
                    addEdge(a, b, cost);
                }
                while (true) {
                    if (dict.isEmpty()) break;
                    if (countOddComponents != 0) break;
                    Edge edge = dict.first();
                    cut(edge.id);
                    int sizeA = TaskE_Pastushka_LinkCutTree.LinkCutTree.size(vertexNodes[edge.a]);
                    int sizeB = TaskE_Pastushka_LinkCutTree.LinkCutTree.size(vertexNodes[edge.b]);
                    if (sizeA % 2 == 0 && sizeB % 2 == 0) {
                        dict.remove(edge);
                    } else {
                        link(edge.id);
                        break;
                    }
                }

                if (countOddComponents == 0) {
                    out.println(dict.first().cost);
                } else {
                    out.println(-1);
                }
            }
        }

        void addEdge(int a, int b, int cost) {
            int newEdgeId = edges.size();
            Edge newEdge = new Edge(a, b, cost, newEdgeId);
            Node newEdgeNode = new Node(newEdgeId, false, cost, 0);
            newEdgeNode.edgeCost = cost;
            edges.add(newEdge);
            edgesNodes.add(newEdgeNode);
            dict.add(newEdge);
            link(newEdgeId);
        }

        void prepareLinkCutTree(int size) {
            vertexNodes = new Node[size];
            for (int i = 0; i < size; ++i) {
                vertexNodes[i] = new Node(i, true, 0, 1);
            }
            edgesNodes = new ArrayList<Node>();
        }

        void link(int edgeId) {
            TaskE_Pastushka_LinkCutTree.LinkCutTree.link(vertexNodes[edges.get(edgeId).a], edgesNodes.get(edgeId));
            TaskE_Pastushka_LinkCutTree.LinkCutTree.link(vertexNodes[edges.get(edgeId).b], edgesNodes.get(edgeId));
        }

        void cut(int edgeId) {
            TaskE_Pastushka_LinkCutTree.LinkCutTree.cut(vertexNodes[edges.get(edgeId).a], edgesNodes.get(edgeId));
            TaskE_Pastushka_LinkCutTree.LinkCutTree.cut(vertexNodes[edges.get(edgeId).b], edgesNodes.get(edgeId));
        }

        class Edge implements Comparable<Edge> {
            int a;
            int b;
            int cost;
            int id;

            public Edge(int a, int b, int cost, int id) {
                this.a = a;
                this.b = b;
                this.cost = cost;
                this.id = id;
            }


            public int compareTo(Edge o) {
                if (cost != o.cost) {
                    return o.cost - cost;
                }
                return id - o.id;
            }

        }

        static class LinkCutTree {
            static void expose(Node t) {
                Node last = null;
                for (Node it = t; it != null; it = it.parent) {
                    splay(it);
                    it.vertexCost -= getSum(last);
                    it.vertexCost += getSum(it.right);
                    it.right = last;
                    last = it;
                    update(it);
                }
                splay(t);
            }

            static void makeRoot(Node t) {
                expose(t);
                t.revert ^= true;
            }

            static void link(Node t, Node parent) {
                makeRoot(t);
                expose(parent);
                t.parent = parent;
                parent.vertexCost += getSum(t);
            }

            static void cut(Node t, Node parent) {
                makeRoot(t);
                expose(parent);
                parent.left.parent = null;
                parent.left = null;
            }

            static Node pathMax(Node v, Node u) {
                makeRoot(v);
                expose(u);
                return u.maxEdge;
            }

            static int size(Node t) {
                makeRoot(t);
                return getSum(t);
            }

            static boolean isConnected(Node t, Node q) {
                expose(t);
                expose(q);
                return t.parent != null;
            }

            static boolean isLeftChild(Node t) {
                return t.parent.left == t;
            }

            static int getSum(Node t) {
                return t == null ? 0 : t.sum;
            }

            static Node max(Node a, Node b) {
                if (a == null || b == null) return a == null ? b : a;
                return a.edgeCost > b.edgeCost ? a : b;
            }

            static void push(Node t) {
                if (t.revert) {
                    t.revert = false;
                    Node temp = t.left;
                    t.left = t.right;
                    t.right = temp;
                    if (t.left != null) {
                        t.left.revert ^= true;
                    }
                    if (t.right != null) {
                        t.right.revert ^= true;
                    }
                }
            }

            static Node getMax(Node t) {
                if (t == null) return null;
                return t.maxEdge;
            }

            static void update(Node t) {
                t.maxEdge = max(t, max(getMax(t.left), getMax(t.right)));
                t.sum = getSum(t.left) + getSum(t.right) + t.vertexCost;
            }

            static void connect(Node t, Node parent, boolean connectLeft) {
                if (connectLeft) {
                    parent.left = t;
                } else {
                    parent.right = t;
                }
                if (t != null) {
                    t.parent = parent;
                }
            }

            static void rotate(Node t) {
                Node p = t.parent;
                Node pp = p.parent;
                boolean isLeft = isLeftChild(t);
                boolean isRootP = p.isRoot();
//            connect(isLeft ? t.right : t.left, p, isLeft);
//            if (!p.isRoot()) {
//                connect(t, pp, isLeftChild(p));
//            } else {
//                t.parent = pp;
//            }

                connect(isLeft ? t.right : t.left, p, isLeft);
                connect(p, t, !isLeft);
                if (!isRootP) {
                    connect(t, pp, p == pp.left);
                } else {
                    t.parent = pp;
                }
//            connect(p, t, !isLeft);
                update(p);
                update(t);
            }

            static void splay(Node t) {
                while (!t.isRoot()) {
                    Node p = t.parent;
                    if (!p.isRoot()) {
                        push(p.parent);
                    }
                    push(p);
                    push(t);
                    if (!p.isRoot()) {
                        rotate(isLeftChild(t) ^ isLeftChild(p) ? t : p);
                    }
                    rotate(t);
                }
                push(t);
                update(t);
            }

        }

        class Node {
            Node parent = null;
            Node left = null;
            Node right = null;
            boolean isVertex;
            int id;
            boolean revert = false;
            int sum;
            Node maxEdge = this;
            int vertexCost;
            int edgeCost;

            public Node(int id, boolean isVertex, int edgeCost, int vertexCost) {
                this.id = id;
                this.isVertex = isVertex;
                this.vertexCost = vertexCost;
                this.sum = vertexCost;
                this.edgeCost = edgeCost;
            }

            boolean isRoot() {
                return parent == null || (parent.left != this && parent.right != this);
            }

        }

    }

    static class InputReader {
        private BufferedReader reader;
        private StringTokenizer stt;

        public InputReader(InputStream stream) {
            reader = new BufferedReader(new InputStreamReader(stream));
        }

        public String nextLine() {
            try {
                return reader.readLine();
            } catch (IOException e) {
                return null;
            }
        }

        public String nextString() {
            while (stt == null || !stt.hasMoreTokens()) {
                stt = new StringTokenizer(nextLine());
            }
            return stt.nextToken();
        }

        public int nextInt() {
            return Integer.parseInt(nextString());
        }

    }
}

