#include <bits/stdc++.h>
using namespace std;
typedef pair<int, int> pii;
const int N = 3e5+10;
const int K = 20;
const int INF = 1e9+10;
vector<pii> G[N], add[N];
int n, m, a[N], b[N], dpdwn[N], dpup[N];
vector<pii> ed;
struct dsu {
vector<int> p;
void init(int sz) {
p.resize(sz+10);
for (int i=0; i<sz+10; ++i) p[i]=i;
}
int f(int x) {
if (p[x] == x) return x;
return p[x]=f(p[x]);
}
void mrg(int x, int y) {
x=f(x), y=f(y);
if (x == y) return;
p[x]=y;
}
};
dsu d;
int up[K][N], mx[K][N], mxd[K][N], tin[N], tout[N], dwn[N], pvl[N], t;
multiset<int> ms[N];
vector<int> ds[N], wgs[N];
void dfs(int v, int p, int w, int mwo) {
up[0][v]=p, mx[0][v]=w, mxd[0][v]=mwo, tin[v]=++t;
for (int j=1; j<K; ++j) up[j][v]=up[j-1][up[j-1][v]];
for (int j=1; j<K; ++j) mx[j][v]=max(mx[j-1][v], mx[j-1][up[j-1][v]]);
for (int j=1; j<K; ++j) mxd[j][v]=min(mxd[j-1][v], mxd[j-1][up[j-1][v]]);
dwn[v]=INF;
for (auto u : G[v]) {
if (u.second == p) continue;
wgs[v].push_back(u.first);
ms[v].insert(u.first);
} sort(wgs[v].begin(), wgs[v].end());
if ((int)wgs[v].size() >= 2) dwn[v]=max(wgs[v][0], wgs[v][1]);
for (auto u : G[v]) {
if (u.second == p) continue;
int k;
if (wgs[v][0] == u.first) {
if ((int)wgs[v].size() == 1) k=INF;
else k=wgs[v][1];
} else k=wgs[v][0];
dfs(u.second, v, u.first, k);
if (dwn[u.second] < INF) dwn[v]=min(dwn[v], max(dwn[u.second], u.first));
ds[v].push_back(max(dwn[u.second], u.first));
} tout[v]=t++, sort(ds[v].begin(), ds[v].end());
}
void dfs2(int v, int p, int ppk) {
pvl[v]=ppk;
if (v != 1) pvl[v]=max(pvl[v], mx[0][v]);
for (auto u : G[v]) {
if (u.second == p) continue;
int tmp=pvl[v];
if ((int)wgs[v].size() >= 3) {
if (u.first == wgs[v][0]) tmp=min(tmp, wgs[v][2]); // wgs[1], wgs[2]
else if (u.first == wgs[v][1]) tmp=min(tmp, wgs[v][2]); // wgs[0], wgs[2]
else tmp=min(tmp, wgs[v][1]); // wgs[0], wgs[1]
}
if (v != 1 && (int)wgs[v].size() >= 2) {
if (u.first == wgs[v][0]) tmp=min(tmp, max(wgs[v][1], mx[0][v]));
else tmp=min(tmp, max(wgs[v][0], mx[0][v]));
}
if ((int)ds[v].size() >= 2) {
if (dwn[u.second] == ds[v][0]) tmp=min(tmp, ds[v][1]);
else tmp=min(tmp, ds[v][0]);
} dfs2(u.second, v, tmp);
}
}
void dfs3(int v, int p) {
dpdwn[v]=INF;
for (auto u : G[v]) {
if (u.second == p) continue;
dfs3(u.second, v);
dpdwn[v]=min(dpdwn[v], max(dpdwn[u.second], u.first));
}
for (auto u : add[v]) dpdwn[v]=min(dpdwn[v], u.first);
}
void dfs4(int v, int p, int px) {
dpup[v]=px;
vector<int> dps;
for (auto u : G[v]) {
if (u.second == p) continue;
dps.push_back(max(dpdwn[u.second], u.first));
} sort(dps.begin(), dps.end());
for (auto u : add[v]) dpup[v]=min(dpup[v], u.first);
for (auto u : G[v]) {
if (u.second == p) continue;
int tp=dpup[v];
if ((int)dps.size() >= 2) {
if (dps[0] == max(dpdwn[u.second], u.first)) tp=min(tp, dps[1]);
else tp=min(tp, dps[0]);
} dfs4(u.second, v, max(u.first, tp));
}
}
bool anc(int v, int u) {
return tin[v] <= tin[u] && tout[u] <= tout[v];
}
int lca(int v, int u) {
if (anc(v, u)) return v;
if (anc(u, v)) return u;
for (int j=K-1; j>=0; --j) {
if (!anc(up[j][v], u)) v=up[j][v];
} return up[0][v];
}
int mwp(int v, int u) {
int l=lca(v, u);
int cv=v, cu=u, res=0;
for (int j=K-1; j>=0; --j) {
if (!anc(up[j][cv], u)) {
res=max(res, mx[j][cv]);
cv=up[j][cv];
}
}
if (cv != l) res=max(res, mx[0][cv]);
for (int j=K-1; j>=0; --j) {
if (!anc(up[j][cu], v)) {
res=max(res, mx[j][cu]);
cu=up[j][cu];
}
}
if (cu != l) res=max(res, mx[0][cu]);
return res;
}
int mwo(int v, int u) {
int l=lca(v, u);
if (v == l) swap(v, u);
int cv=v, cu=u, res=dwn[v];
for (int j=K-1; j>=0; --j) {
if (!anc(up[j][cv], u)) {
res=min(res, mxd[j][cv]);
cv=up[j][cv];
}
}
for (int j=K-1; j>=0; --j) {
if (!anc(up[j][cu], v)) {
res=min(res, mxd[j][cu]);
cu=up[j][cu];
}
}
if (u == l) {
res=min(res, dwn[v]);
int tpw=mx[0][cv];
int k;
if (u == 1) k=INF;
else k=mx[0][u];
if (u != 1) res=min(res, max(k, pvl[u]));
//cout<<"HERE "<<u<<" || "<<k<<" || "<<pvl[u]<<"\n";
if ((int)wgs[u].size() >= 3) {
if (tpw == wgs[u][0]) res=min(res, wgs[u][2]); // wgs[1], wgs[2]
else if (tpw == wgs[u][1]) res=min(res, wgs[u][2]); // wgs[0], wgs[2]
else res=min(res, wgs[u][1]); // wgs[0], wgs[1]
}
if (k < INF && (int)wgs[u].size() >= 2) {
if (tpw == wgs[u][0]) res=min(res, max(wgs[u][1], k)); // wgs[1], k
else res=min(res, max(wgs[u][0], k));
}
//cout<<"size "<<ds[u].size()<<" ==> "<<ds[u][0]<<", "<<ds[u][1]<<"\n";
if ((int)ds[u].size() >= 2) {
if (dwn[cv] == ds[u][0]) res=min(res, ds[u][1]);
else res=min(res, ds[u][0]);
}
} else {
res=min(res, dwn[u]);
if (l != 1) res=min(res, mx[0][l]);
res=min({res, dwn[v], dwn[u]});
int au=-1, av=-1;
av=mx[0][cv], ms[l].erase(ms[l].find(mx[0][cv]));
au=mx[0][cu], ms[l].erase(ms[l].find(mx[0][cu]));
if (!ms[l].empty()) res=min(res, *ms[l].begin());
ms[l].insert(au), ms[l].insert(av);
} return res;
}
bool ok=false;
void init(int _n, int _m, vector<int> x, vector<int> y, vector<int> w) {
n=_n, m=_m;
for (int i=0; i<m; ++i) {
++x[i], ++y[i];
a[i+1]=x[i], b[i+1]=y[i];
ed.push_back({w[i], i+1});
} sort(ed.begin(), ed.end());
d.init(n+10);
for (auto u : ed) {
if (d.f(a[u.second]) == d.f(b[u.second])) {
add[a[u.second]].push_back({u.first, b[u.second]});
add[b[u.second]].push_back({u.first, a[u.second]});
} else {
d.mrg(a[u.second], b[u.second]);
G[a[u.second]].push_back({u.first, b[u.second]});
G[b[u.second]].push_back({u.first, a[u.second]});
}
} dfs(1, 1, 0, INF);
dfs2(1, 1, INF);
dfs3(1, 1);
dfs4(1, 1, INF);
}
int getMinimumFuelCapacity(int x, int y) {
++x, ++y;
if (d.f(x) != d.f(y)) return -1;
int val=max(mwp(x, y), min({mwo(x, y), dpup[x], dpup[y], dpdwn[x], dpdwn[y]}));
if (val >= INF) return -1;
return val;
}
