NOI2014 魔法森林

#include <cstdio>

#include <algorithm>

using namespace std;

struct Data {
    int v, id;

    Data() {}

    Data(int v, int id) : v(v), id(id) {}

    bool operator<(const Data& x) const
    { return v < x.v; }
};

const int N = 150010;

struct LinkCutTree {
    struct Node {
        bool rev;
        Data v, mex;
        union {
            struct {
                Node *ls, *rs;
            };
            Node* ch[2];
        };
        Node *prt, *path;

        bool relation() const
        { return this == prt->rs; }

        void pushDown() {
            if (rev) {
                rev = false;
                swap(ls, rs);
                if (ls)
                    ls->rev = !ls->rev;
                if (rs)
                    rs->rev = !rs->rev;
            }
        }

        void update() {
            mex = v;
            if (ls)
                mex = max(mex, ls->mex);
            if (rs)
                mex = max(mex, rs->mex);
        }

        void rotate() {
            if (prt->prt)
                prt->prt->pushDown();
            prt->pushDown();
            pushDown();
            path = prt->path;
            prt->path = NULL;
            Node* p = prt;
            bool f = relation();
            if (p->prt)
                p->prt->ch[p->relation()] = this;
            prt = p->prt;
            p->ch[f] = ch[!f];
            if (ch[!f])
                ch[!f]->prt = p;
            ch[!f] = p;
            p->prt = this;
            p->update();
            update();
        }

        void splay() {
            while (prt) {
                if (!prt->prt)
                    return rotate();
                prt->prt->pushDown();
                prt->pushDown();
                if (relation() == prt->relation()) {
                    prt->rotate();
                    rotate();
                } else {
                    rotate();
                    rotate();
                }
            }
        }

        void expose() {
            splay();
            pushDown();
            if (rs) {
                rs->path = this;
                rs->prt = NULL;
                rs = NULL;
                update();
            }
        }

        bool splice() {
            splay();
            if (!path)
                return false;
            path->expose();
            path->rs = this;
            prt = path;
            path = NULL;
            prt->update();
            return true;
        }

        void access() {
            expose();
            while (splice());
        }

        void evert() {
            access();
            splay();
            rev = !rev;
        }

        Data query() {
            access();
            splay();
            return mex;
        }

        Node* find() {
            access();
            splay();
            Node* p = this;
            while (p->pushDown(), p->ls)
                p = p->ls;
            p->splay();
            return p;
        }
    };

    Node ver[N];

    void link(int u, int v) {
//      fprintf(stderr, "LINK %d %d\n", u, v);
        ver[u].evert();
        ver[u].path = ver + v;
    }

    void cut(int u, int v) {
//      fprintf(stderr, "CUT %d %d\n", u, v);
        ver[u].evert();
        ver[v].access();
        ver[u].expose();
//      fprintf(stderr, "%p\n", ver[v].path);
        ver[v].path = NULL;
    }

    bool connected(int u, int v) {
        return ver[u].find() == ver[v].find();
    }

    Data query(int u, int v) {
        ver[u].evert();
//      fprintf(stderr, "Q %d\n", ver[v].query().v);
        return ver[v].query();
    }
};

int n;
int eu[N], ev[N];

struct DynamicMST {
    int sum, ecnt;
    LinkCutTree tree;

    void add(int u, int v, int w) {
        ++ecnt;
        eu[ecnt] = u;
        ev[ecnt] = v;
        tree.ver[n + ecnt].v = tree.ver[n + ecnt].mex = Data(w, ecnt);
        if (!tree.connected(u, v)) {
            tree.link(n + ecnt, u);
            tree.link(n + ecnt, v);
            sum += w;
            return;
        }
        Data mex = tree.query(u, v);
//      fprintf(stderr, "Q %d %d %d\n", mex.v, w, mex.id);
        if (mex.v <= w)
            return;
        sum -= mex.v;
        tree.cut(n + mex.id, eu[mex.id]);
        tree.cut(n + mex.id, ev[mex.id]);
        tree.link(n + ecnt, u);
        tree.link(n + ecnt, v);
        sum += w;
    }
};

struct Edge {
    int u, v, a, b;

    bool operator<(const Edge& x) const {
        return a < x.a;
    }
};

DynamicMST mst;

int m;
Edge e[N];

int main() {
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= m; ++i) {
        scanf("%d%d%d%d", &e[i].u, &e[i].v, &e[i].a, &e[i].b);
    }
    int ans = -1;
    sort(e + 1, e + m + 1);
    for (int i = 1; i <= m; ++i) {
        mst.add(e[i].u, e[i].v, e[i].b);
        if (mst.tree.connected(1, n)) {
            Data cur = mst.tree.query(1, n);
            if ((ans == -1 || cur.v + e[i].a < ans)) {
//              fprintf(stderr, "%d %d\n", i, cur.v);
                ans = cur.v + e[i].a;
            }
        }
    }
    printf("%d\n", ans);
    return 0;
}