namespace Circle_Square_Tree{//圆方树 无向仙人掌 圆点为原仙人掌点，方点用于统合除顶部点外的同环点 一般1号点为圆方树的根
    struct node{
        vector<int > e;//圆方树出边
        void clear() {
            e.clear();
        }
    }tree[MAXN], tmp;
    vector<pair<int, pair<int, long long> > >*g;
    int N, tot, calc;
    int dfn[MAXN], low[MAXN], stack[MAXN];
    bool instack[MAXN];
    void init(int n) {
        calc = 0;
        while (tot){
            tree[tot].clear();
            tot --;
        }
        for (int i = 1; i <= n ; i++)
            dfn[i] = low[i] = instack[i] = 0;
        stack[0] = 0;
        tot = N = n;
    }
    inline bool is_circle_point(int x) {
        return x <= N;
    }
    inline bool is_square_point(int x) {
        return x > N;
    }
    void insert(int x, int y) {
        tree[x].e.push_back(y);
    }
    void dfs(int x, int fa_edge_id) {
        dfn[x] = low[x] = ++calc, stack[++stack[0]] = x, instack[x] = 1;
        //for (auto u:g[x]) {
        for (int ii = 0; ii < g[x].size(); ii ++){
            pair<int, pair<int, long long> > u = g[x][ii];
            if (!dfn[u.first]) {
                dfs(u.first, u.second.first);
                low[x] = min(low[x], low[u.first]);
                if (dfn[x] <= low[u.first]) {
                    vector<int> d;
                    do {
                        instack[stack[stack[0]]] = 0;
                        d.push_back(stack[stack[0]--]);
                    } while (stack[stack[0] + 1] != u.first);
                    if (dfn[x] != low[u.first]) {
                        insert(x, u.first);
                        continue;
                    }
                    ++tot;
                    reverse(d.begin(), d.end());
                    for (int i = 0; i < d.size(); i++)
                        insert(tot, d[i]);
                    insert(x, tot);
                }
            } else
            if (u.second.first != fa_edge_id) {
                low[x] = min(low[x], dfn[u.first]);
            }
        }
    }
    void build(vector<pair<int, pair<int, long long> > >*G, int n){
        init(n);
        g = G;
        for (int i = 1; i <= N ;  i++)
            if (!dfn[i])
                dfs(i, 0);
    }
}