Problem: After a successful field test, Heidi is considering deploying a trap along some Corridor, possibly not the first one. She wants to avoid meeting the Daleks inside the Time Vortex, so for abundance of caution she considers placing the traps only along those Corridors that are not going to be used according to the current Daleks' plan – which is to use a minimum spanning tree of Corridors. Heidi knows that all energy requirements for different Corridors are now different, and that the Daleks have a single unique plan which they are intending to use.

Your task is to calculate the number E_{max}(c), which is defined in the same way as in the easy version – i.e., the largest e ≤ 10^9 such that if we changed the energy of corridor c to e, the Daleks might use it – but now for every corridor that Heidi considers. 

Input

The first line: number n of destinations, number m of Time Corridors (2 ≤ n ≤ 10^5, n - 1 ≤ m ≤ 10^6). The next m lines: destinations a, b and energy e (1 ≤ a, b ≤ n, a ≠ b, 0 ≤ e ≤ 10^9).

No pair \\{a, b\} will repeat. The graph is guaranteed to be connected. All energy requirements e are distinct.

Output

Output m-(n-1) lines, each containing one integer: E_{max}(c_i) for the i-th Corridor c_i from the input that is not part of the current Daleks' plan (minimum spanning tree).

Example

Input

3 3
1 2 8
2 3 3
3 1 4


Output

4

Note

If m = n-1, then you need not output anything.

Solution (in JAVA):

Solution:
//package math_codet;

import java.io.OutputStream;
import java.io.IOException;
import java.io.InputStream;
import java.io.PrintWriter;
import java.util.Arrays;
import java.io.IOException;
import java.util.TreeSet;
import java.util.ArrayList;
import java.util.Comparator;
import java.io.InputStream;
/**
 * Built using CHelper plug-in
 * Actual solution is at the top
 *
 * @author Aman Kumar Singh
 */
public class lets_do {
    public static void main(String[] args) {
        InputStream inputStream = System.in;
        OutputStream outputStream = System.out;
        InputReader in = new InputReader(inputStream);
        PrintWriter out = new PrintWriter(outputStream);
        EMinimumSpanningTreeForEachEdge solver = new EMinimumSpanningTreeForEachEdge();
        solver.solve(1, in, out);
        out.close();
    }
    static class EMinimumSpanningTreeForEachEdge {
        PrintWriter out;
        InputReader in;
        TreeSet<Integer>[] tset;
        ArrayList<Edge>[] tree;
        long[] val;
        long[] segtree;
        int[] depth;
        int[] heavy;
        int[] head;
        int[] pos;
        int[] parent;
        int cur_pos = 0;
        int n;
        final Comparator<Pair> com = new Comparator<Pair>() {
            public int compare(Pair a, Pair b) {
                if (Integer.compare(a.x, b.x) != 0)
                    return Integer.compare(a.x, b.x);
                else
                    return Integer.compare(a.y, b.y);
            }
        };
        void build() {
            int i = 0, j = 0;
            for (i = 0; i < n; i++)
                segtree[n + pos[i]] = val[i];
            for (i = n - 1; i > 0; i--)
                segtree[i] = Math.max(segtree[i << 1], segtree[i << 1 | 1]);
        }
        long st_query(int l, int r) {
            long res = 0;
            for (l += n, r += n; l < r; l >>= 1, r >>= 1) {
                if ((l & 1) == 1) res = Math.max(segtree[l++], res);
                if ((r & 1) == 1) res = Math.max(segtree[--r], res);
            }
            return res;
        }
        int dfs(int v) {
            int size = 1;
            int max_c_size = 0;
            for (Edge e : tree[v]) {
                int c = e.other(v);
                if (c != parent[v]) {
                    parent[c] = v;
                    val[c] = e.wt;
                    depth[c] = depth[v] + 1;
                    int c_size = dfs(c);
                    size += c_size;
                    if (c_size > max_c_size) {
                        max_c_size = c_size;
                        heavy[v] = c;
                    }
                }
            }
            return size;
        }
        void decompose(int v, int h) {
            head[v] = h;
            pos[v] = cur_pos++;
            if (heavy[v] != -1)
                decompose(heavy[v], h);
            for (Edge e : tree[v]) {
                int c = e.other(v);
                if (c != parent[v] && c != heavy[v])
                    decompose(c, c);
            }
        }
        long query(int a, int b) {
            long res = 0;
            for (; head[a] != head[b]; b = parent[head[b]]) {
                if (depth[head[a]] > depth[head[b]]) {
                    int t = a;
                    a = b;
                    b = t;
                }
                long cur_heavy_path_max = st_query(pos[head[b]], pos[b] + 1);
                res = Math.max(cur_heavy_path_max, res);
            }
            if (depth[a] > depth[b]) {
                int t = a;
                a = b;
                b = t;
            }
            long last_heavy_path_max = st_query(pos[a] + 1, pos[b] + 1);
            res = Math.max(last_heavy_path_max, res);
            return res;
        }
        public void solve(int testNumber, InputReader in, PrintWriter out) {
            this.out = out;
            this.in = in;
            n = ni();
            int m = ni();
            int[][] edges = new int[n][2];
            tree = new ArrayList[n];
            val = new long[n];
            segtree = new long[2 * n];
            depth = new int[n];
            heavy = new int[n];
            parent = new int[n];
            head = new int[n];
            pos = new int[n];
            Arrays.fill(heavy, -1);
            int i = 0;
            tset = new TreeSet[n];
            for (i = 0; i < n; i++)
                tree[i] = new ArrayList<Edge>();
            DSU ob = new DSU(n);
            for (i = 0; i < n; i++)
                tset[i] = new TreeSet<>();
            Pair[] hola = new Pair[m];
            int[][] store = new int[m][3];
            for (i = 0; i < m; i++) {
                int u = ni() - 1;
                int v = ni() - 1;
                store[i][0] = u;
                store[i][1] = v;
                store[i][2] = ni();
                hola[i] = new Pair(store[i][2], i);
            }
            Arrays.sort(hola, com);
            long wt = 0;
            for (i = 0; i < m; i++) {
                int u = store[hola[i].y][0];
                int v = store[hola[i].y][1];
                long w = hola[i].x;
                if (ob.find(u) != ob.find(v)) {
                    ob.unite(u, v);
                    Edge e = new Edge(u, v, w);
                    tree[u].add(e);
                    tree[v].add(e);
                    tset[u].add(v);
                    tset[v].add(u);
                    wt += w;
                }
            }
            dfs(0);
            decompose(0, 0);
            build();
            for (i = 0; i < m; i++) {
                int u = store[i][0];
                int v = store[i][1];
                if (tset[u].contains(v))
                    continue;
                else {
                    long lol = query(u, v);
                    pn(lol);
                }
            }
        }
        int ni() {
            return in.nextInt();
        }
        void pn(Object o) {
            out.println(o);
        }
        class DSU {
            int[] rank;
            int[] parent;
            public DSU(int n) {
                rank = new int[n];
                parent = new int[n];
                make_set(n);
            }
            void make_set(int n) {
                int i = 0;
                for (i = 0; i < n; i++)
                    parent[i] = i;
            }
            int find(int x) {
                if (parent[x] != x)
                    parent[x] = find(parent[x]);
                return parent[x];
            }
            void unite(int x, int y) {
                int xRoot = find(x), yRoot = find(y);
                if (xRoot == yRoot)
                    return;
                if (rank[xRoot] < rank[yRoot])
                    parent[xRoot] = yRoot;
                else if (rank[yRoot] < rank[xRoot])
                    parent[yRoot] = xRoot;
                else {
                    parent[yRoot] = xRoot;
                    rank[xRoot] = rank[xRoot] + 1;
                }
            }
        }
        class Pair {
            int x;
            int y;
            Pair(int p, int q) {
                x = p;
                y = q;
            }
        }
        class Edge {
            int u;
            int v;
            long wt;
            Edge(int a, int b, long w) {
                u = a;
                v = b;
                wt = w;
            }
            int other(int x) {
                return u ^ v ^ x;
            }
        }
    }
    static class InputReader {
        private InputStream stream;
        private byte[] buf = new byte[1024];
        private int curChar;
        private int numChars;
        public InputReader(InputStream stream) {
            this.stream = stream;
        }
        public int read() {
            if (numChars == -1)
                throw new UnknownError();
            if (curChar >= numChars) {
                curChar = 0;
                try {
                    numChars = stream.read(buf);
                } catch (IOException e) {
                    throw new UnknownError();
                }
                if (numChars <= 0)
                    return -1;
            }
            return buf[curChar++];
        }
        public int nextInt() {
            return Integer.parseInt(next());
        }
        public String next() {
            int c = read();
            while (isSpaceChar(c))
                c = read();
            StringBuffer res = new StringBuffer();
            do {
                res.appendCodePoint(c);
                c = read();
            } while (!isSpaceChar(c));
            return res.toString();
        }
        private boolean isSpaceChar(int c) {
            return c == ' ' || c == '\n' || c == '\r' || c == '\t' || c == -1;
        }
    }
}