/*
* 思路:
* 将所有边按照a来进行升序排序,依次从小到大将边加入,在已经加入边的图上找1到n间路径中b的最大值,求出的b最大值和当前枚举的a的和用于更新全局的最小值答案
* 原始点id从1到n, 权值是0,将边抽象成点,如果有一条边
* (A, B), 权值为W,边id是i, 将其抽象为一个权值是W的点, 添加边(A, B), 就是在图上添加(A, i+(n+1))和(B, i+(n+1)) 这两条边,这样问题就转换为
* 动态求节点1到节点n之间路径上b的点权值的最大值,当添加一条边(A,B)时候,如果发现AB已经连通,再添加(A,B)会形成环,此时找到图上A,B之间路径上最大
* 的点权值max_w(对应原来图里面边的最大权值),如果max_w > W, 则可以将这条最大的边删掉,然后添加(A,B), 这样不会影响连通性,也不会造成漏解,如果max_w <= W
* 那(A,B)这条边没有添加的必要,因为不可能因为添加这条边得到更优解,用这样的策略可以一直保持图是没有环的,形状始终是森林,这样就可以用动态树来维护
* 这个图,利用动态树的特性快速求路径上的最大点权值
*
*/
#include <algorithm>
using namespace std;
// 最大节点个数,节点从1开始编号
const int MAX_NODE_NUM = 200005;
// Splay节点
struct Node {
int child[2]; // 两个子节点id
int parent; // 父节点id
int val; // 节点的数值
int max_val; // 区间上的最大值
int max_node_idx; // 数值最大的点的编号
int rev_flag; // 区间翻转标记
} __node_pool[MAX_NODE_NUM];
int stack[MAX_NODE_NUM];
// 最大的边数量
const int MAX_EDGE_NUM = 100005;
// 边结构体
struct edge_node {
int node1, node2, a, b;
bool operator < (const edge_node& other) const {
return a < other.a;
}
} __edge_nodes[MAX_EDGE_NUM];
int n, m;
// 并查集用的数组
int pp[MAX_NODE_NUM];
// 当前节点的左右子树做翻转操作
void __process_rev(int idx) {
Node& node = __node_pool[idx];
int t = node.child[0];
node.child[0] = node.child[1];
node.child[1] = t;
}
// 归并两颗子树的结果
void __push_up(int idx) {
Node& node = __node_pool[idx];
int ans = node.val;
int ans_idx = idx;
if (node.child[0] != 0) {
if (__node_pool[node.child[0]].max_val > ans) {
ans_idx = __node_pool[node.child[0]].max_node_idx;
ans = __node_pool[node.child[0]].max_val;
}
}
if (node.child[1] != 0) {
if (__node_pool[node.child[1]].max_val > ans) {
ans_idx = __node_pool[node.child[1]].max_node_idx;
ans = __node_pool[node.child[1]].max_val;
}
}
node.max_val = ans;
node.max_node_idx = ans_idx;
}
// 下传区间翻转lazy标记
void __push_down_rev_flag(int idx) {
Node& node = __node_pool[idx];
if (node.rev_flag == 0) {
return;
}
if (node.child[0] != 0) {
__node_pool[node.child[0]].rev_flag ^= 1;
}
if (node.child[1] != 0) {
__node_pool[node.child[1]].rev_flag ^= 1;
}
}
// 区间反转的push_down操作
void __push_down_rev(int idx) {
Node& node = __node_pool[idx];
if (node.rev_flag == 0) {
return;
}
__push_down_rev_flag(idx);
if (node.child[0] != 0) {
__process_rev(node.child[0]);
}
if (node.child[1] != 0) {
__process_rev(node.child[1]);
}
node.rev_flag = 0;
}
// 统一的push_down函数
void __push_down(int idx) {
__push_down_rev(idx);
}
// 判断节点是否是其所在的splay的根节点
bool is_splay_root(int idx) {
int parent = __node_pool[idx].parent;
return idx != __node_pool[parent].child[0] && idx != __node_pool[parent].child[1];
}
// 修改lazy标记的数值
void reverse_flag(int idx) {
Node& node = __node_pool[idx];
node.rev_flag ^= 1;
__process_rev(idx); // 修改了lazy标记,一定要让标记的影响在当前节点上作用一次
}
// 统一的左旋和右旋函数,将编号为x对应的节点向上一层旋转
void __rotate(int x) {
int y = __node_pool[x].parent, z = __node_pool[y].parent;
int k1 = __node_pool[y].child[1] == x, k2 = __node_pool[z].child[1] == y;
// 如果y是splay的根,那z的子节点指针表示的是实边信息,不能做修改z的子节点信息
if (!is_splay_root(y)) {
__node_pool[z].child[k2] = x;
}
__node_pool[x].parent = z;
__node_pool[y].child[k1] = __node_pool[x].child[k1^1];
__node_pool[__node_pool[x].child[k1^1]].parent = y;
__node_pool[x].child[k1^1] = y;
__node_pool[y].parent = x;
__push_up(y);
__push_up(x);
}
// 将x所在实边路径对应的Splay上的lazy标记都使用掉,然后将x旋转到Splay的根
void splay(int x) {
int top = 0;
int r = x;
stack[++top] = x;
while (!is_splay_root(r)) {
r = __node_pool[r].parent;
stack[++top] = r;
}
// 从上到下push_down一次
while (top) {
__push_down(stack[top--]);
}
// 将x旋转到所属的splay的根上
while (!is_splay_root(x)) {
int y = __node_pool[x].parent;
int z = __node_pool[y].parent;
if (!is_splay_root(y)) {
if ((__node_pool[y].child[1] == x) ^ (__node_pool[z].child[1] == y)) {
__rotate(x);
} else {
__rotate(y);
}
}
__rotate(x);
}
}
// 将节点x所属于的动态树的根r和x之间的路径变为实边路径, 同时将x变为其最后所属的splay的根
void access(int x) {
int z = x;
for (int y = 0; x != 0; y = x, x = __node_pool[x].parent) {
splay(x);
__node_pool[x].child[1] = y;
__push_up(x);
}
splay(z);
}
// 将x变为整个动态树的根
void make_root(int x) {
access(x);
reverse_flag(x);
}
// 找到x所属的动态树的根节点id, 然后将这个节点旋转到其所属的Splay的根位置
int find_root(int x) {
access(x);
while (__node_pool[x].child[0] != 0) {
__push_down(x);
x = __node_pool[x].child[0];
}
splay(x);
return x;
}
// 将两个节点x, y之间的路径变为实边路径, 且y变为其所属的splay的根
void split(int x, int y) {
make_root(x);
access(y);
}
// 如果x和y不在一颗动态树上,添加一条从x到y的虚边
void link(int x, int y) {
make_root(x);
if (find_root(y) != x) {
__node_pool[x].parent = y;
}
}
// 如果xy之前在动态树上存在边相连,将该边断掉
void cut(int x, int y) {
make_root(x);
if (find_root(y) == x && __node_pool[y].parent == x && __node_pool[y].child[0] == 0) {
__node_pool[x].child[1] = __node_pool[y].parent = 0;
__push_up(x);
}
}
int get_root(int node) {
if (pp[node] == node) {
return node;
}
pp[node] = get_root(pp[node]);
return pp[node];
}
void merge(int a, int b) {
int root1 = get_root(a), root2 = get_root(b);
if (root1 != root2) {
pp[root1] = root2;
}
}
bool in_same_set(int a, int b) {
return get_root(a) == get_root(b);
}
// 获取动态树上从node1到node2路径上权值最大的点的编号
int get_max_dis_node_idx(int node1, int node2) {
split(node1, node2);
return __node_pool[node2].max_node_idx;
}
// 获取动态树上从node1到node2路径上最大的点权值
int get_max_dis(int node1, int node2) {
split(node1, node2);
return __node_pool[node2].max_val;
}
// 添加一条边
void add_edge(int node1, int node2, int edge_node, int w) {
if (in_same_set(node1, node2)) {
int max_node_idx = get_max_dis_node_idx(node1, node2);
int max_weight = __node_pool[max_node_idx].val;
if (max_weight <= w) {
// 当前那这条边没有加的必要,不会让答案更优
return;
}
cut(max_node_idx, __edge_nodes[max_node_idx - (n+1)].node1);
cut(max_node_idx, __edge_nodes[max_node_idx - (n+1)].node1);
}
link(edge_node, node1);
link(edge_node, node2);
}
int main() {
//freopen("/Users/grh/Programming/CLionProjects/SimpleTest/input.txt", "r", stdin);
int node1, node2, a, b;
scanf("%d %d", &n, &m);
for (int i = 0; i < m; i++) {
scanf("%d %d %d %d", &(__edge_nodes[i].node1), &(__edge_nodes[i].node2), &(__edge_nodes[i].a), &(__edge_nodes[i].b));
}
// 按照a权值进行排序
sort(__edge_nodes, __edge_nodes + m);
// 一开始图上已经存在的原始的点权值全部都是0, 编号1到n
for (int i = 1; i <= n; i++) {
__node_pool[i].val = 0;
__node_pool[i].max_val = 0;
__node_pool[i].max_node_idx = i;
pp[i] = i;
}
// 边抽象出来的点的编号n+1 到 n+m
for (int i = 0; i < m; i++) {
__node_pool[i+n+1].val = __edge_nodes[i].b;
__node_pool[i+n+1].max_val = __edge_nodes[i].b;
__node_pool[i+n+1].max_node_idx = i+n+1;
pp[i+n+1] = i+n+1;
}
int ans = 0x7fffffff;
int i = 0;
while (i < m) {
int j = i;
int wei_a = __edge_nodes[i].a;
while (j < m && __edge_nodes[j].a == wei_a) {
if (__edge_nodes[j].node1 != __edge_nodes[j].node2) {
add_edge(__edge_nodes[j].node1, __edge_nodes[j].node2, j+(n+1), __edge_nodes[j].b);
merge(__edge_nodes[j].node1, __edge_nodes[j].node2);
}
j += 1;
}
if (in_same_set(1, n)) {
ans = min(ans, wei_a + get_max_dis(1, n));
}
i = j;
}
if (ans != 0x7fffffff) {
printf("%d\n", ans);
} else {
printf("-1\n");
}
return 0;
}