此题可以用spfa，也可以用LCT。
可spfa跑得比LCT快……
学习了一下怎么把边权变成点权：
新建一个点表示边，这个点的点权就是边权值
原来的点的权值为0（根据题目需要可以为其他值）
添加一条边时，连接两端的点
删除一条边时，需要找到这条边对应的点编号，两端删除 1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
using namespace std;
struct node {
int u,v,a,b;
bool operator<(const node &res) const{
return a<res.a;
}
} edge[100005];
int FA[50005];
int val[150005],mx[150005],po[150005];
int ch[150005][2],fa[150005];
bool reversed[150005];
int sta[150005],top;
int n,m,ans=1e9;
inline int read() {
char ch=0;int sum=0;
while (ch>'9'||ch<'0') ch=getchar();
while (ch>='0'&&ch<='9') sum=sum*10+ch-'0',ch=getchar();
return sum;
}
int find(int x) {
if (FA[x]!=x) FA[x]=find(FA[x]);
return FA[x];
}
inline void Union(int x,int y) {
FA[find(x)]=find(y);
}
inline void reverse(int x) {
swap(ch[x][0],ch[x][1]);
reversed[x]^=1;
}
inline void pushdown(int x) {
if (reversed[x]) {
if (ch[x][0]) reverse(ch[x][0]);
if (ch[x][1]) reverse(ch[x][1]);
reversed[x]=0;
}
}
inline void pushup(int x) {
int pp=x,tmp=val[x];
if (mx[ch[x][1]]>tmp) pp=po[ch[x][1]],tmp=mx[ch[x][1]];
if (mx[ch[x][0]]>tmp) pp=po[ch[x][0]],tmp=mx[ch[x][0]];
po[x]=pp;mx[x]=tmp;
}
inline bool notroot(int x) {
return (ch[fa[x]][0]==x)||(ch[fa[x]][1]==x);
}
inline void rotate(int x) {
int fa1=fa[x],fa2=fa[fa1],side=(ch[fa1][1]==x),c=ch[x][side^1];
fa[x]=fa2;if (notroot(fa1)) ch[fa2][ch[fa2][1]==fa1]=x;
ch[fa1][side]=c;if (c) fa[c]=fa1;
fa[fa1]=x;ch[x][side^1]=fa1;
pushup(fa1);pushup(x);
}
inline void splay(int x) {
int u=x,top=0;
while (notroot(u)) sta[++top]=u,u=fa[u];
sta[++top]=u;
while (top) pushdown(sta[top--]);
while (notroot(x)) {
int fa1=fa[x],fa2=fa[fa1];
if (notroot(fa1)) {
if ((ch[fa2][0]==fa1)^(ch[fa1][0]==x)) rotate(x);
else rotate(fa1);
}
rotate(x);
}
}
inline void access(int x) {
int u=0;
while (x!=0) {
splay(x);
ch[x][1]=u;
pushup(x);
u=x;
x=fa[x];
}
}
inline void makeroot(int x) {
access(x);splay(x);
reverse(x);
}
inline int findroot(int x) {
access(x);splay(x);
while (ch[x][0]) pushdown(x),x=ch[x][0];
splay(x);
return x;
}
inline void split(int x,int y) {
makeroot(x);
access(y);splay(y);
}
inline void link(int x,int y) {
makeroot(x);
if (findroot(y)!=x) fa[x]=y;
}
inline void cut(int x,int y) {
makeroot(x);
if (findroot(y)==x && fa[y]==x && ch[x][1]==y) {
fa[y]=ch[x][1]=0;
pushup(x);
}
}
inline void addedge(int i) {
int u=edge[i].u,v=edge[i].v;
if (find(u)!=find(v)) {
Union(u,v);
val[i+n]=mx[i+n]=edge[i].b;
po[i+n]=i+n;
link(u,i+n);
link(v,i+n);
}
else {
split(u,v);
if (edge[i].b<mx[v]) {
int w=po[v];
cut(w,edge[w-n].u);
cut(w,edge[w-n].v);
val[i+n]=mx[i+n]=edge[i].b;
po[i+n]=i+n;
link(u,i+n);
link(v,i+n);
}
}
}
int main() {
n=read(),m=read();
for (int i=1;i<=m;i++) {
edge[i].u=read();edge[i].v=read();
edge[i].a=read();edge[i].b=read();
}
sort(edge+1,edge+m+1);
for (int i=1;i<=n;i++) FA[i]=po[i]=i;
for (int i=1;i<=m;i++) {
addedge(i);
while (i<m && edge[i].a==edge[i+1].a) addedge(++i);
if (find(1)==find(n)) {
split(1,n);
ans=min(ans,edge[i].a+mx[n]);
}
}
if (ans==1e9) puts("-1");
else printf("%d",ans);
return 0;
}