#include "swap.h"
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define pb push_back
#define INF 1100000000
#define sz(x) (int)(x).size()
#define mp make_pair
#define all(x) (x).begin(),(x).end()
#define ii pair<int,int>
int n,m;
vector<pair<int,ii> > e,ne;
struct ufds {
vector<int> p;
ufds(int n) {
p.assign(n,0);
for (int i=0;i<n;i++) p[i]=i;
}
int find(int x) {
return (p[x]==x)?x:(p[x]=find(p[x]));
}
void join(int x,int y) {
int a=find(x),b=find(y);
if (a!=b) p[a]=b;
}
bool same(int x,int y) {
return (find(x)==find(y));
}
};
vector<ii> adj[100005],fadj[100005];
int p[100005],pre[100005],bd[100005],dp[100005],cur;
void form(int v,int d) {
pre[v]=cur++;
dp[v]=d;
for (ii x:adj[v]) {
if (x.first==p[v]) continue;
p[x.first]=v;
form(x.first,d+1);
}
bd[v]=cur-1;
}
void add_edge(int a,int b,int c) {
adj[a].pb(mp(b,c));
adj[b].pb(mp(a,c));
}
int dist[100005],pv[100005];
void dfs(int v,int d) {
dist[v]=d;
for (ii x:adj[v]) {
if (dist[x.first]==INF) {
pv[x.first]=v;
dfs(x.first,max(d,x.second));
}
}
}
vector<int> path;
bool inside(int x,int a,int b) {
return (x>=a && x<=b);
}
vector<int> vec;
int shortest_path(int a,int b) {
if (dp[a]<dp[b]) swap(a,b);
pv[a]=-1;
for (int i=0;i<n;i++) dist[i]=INF;
dfs(a,0);
int c=b;
path.clear();
while(c!=-1) {
path.pb(c);
c=pv[c];
}
int onpath=INF;
for (int i=1;i<sz(path)-1;i++) {
for (ii x:fadj[path[i]]) {
if (x.first==path[i-1] || x.first==path[i+1]) continue;
onpath=min(onpath,x.second);
}
}
int ans=max(dist[b],onpath);
vec.clear();
for (ii x:fadj[a]) {
if (x.first==path[sz(path)-2]) continue;
vec.pb(x.second);
}
sort(all(vec));
if (sz(vec)>=2) {
ans=min(ans,max(dist[b],vec[1]));
}
vec.clear();
for (ii x:fadj[b]) {
if (x.first==path[1]) continue;
vec.pb(x.second);
}
sort(all(vec));
if (sz(vec)>=2) {
ans=min(ans,max(dist[b],vec[1]));
}
if (p[path[1]]==b) {
for (auto edge:ne) {
int w=edge.first;
int ea=edge.second.first;
int eb=edge.second.second;
if (inside(pre[ea],pre[a],bd[a]) && inside(pre[eb],pre[a],bd[a])) continue;
if (!inside(pre[ea],pre[path[1]],bd[path[1]]) && !inside(pre[eb],pre[path[1]],bd[path[1]])) continue;
ans=min(ans,max(dist[b],w));
break;
}
} else {
for (auto edge:ne) {
int w=edge.first;
int ea=edge.second.first;
int eb=edge.second.second;
if (inside(pre[ea],pre[a],bd[a]) && inside(pre[eb],pre[a],bd[a])) continue;
if (inside(pre[ea],pre[b],bd[b]) && inside(pre[eb],pre[b],bd[b])) continue;
ans=min(ans,max(dist[b],w));
break;
}
}
return ans;
}
void mst() {
sort(all(e));
ufds u(n);
for (int i=0;i<m;i++) {
int a=e[i].second.first,b=e[i].second.second;
fadj[a].pb(mp(b,e[i].first));
fadj[b].pb(mp(a,e[i].first));
if (!u.same(a,b)) {
u.join(a,b);
add_edge(a,b,e[i].first);
// printf("add %d %d to Tree\n", a,b);
} else {
ne.pb(e[i]);
}
}
p[0]=-1;
form(0,0);
}
void init(int N, int M, vector<int> U, vector<int> V, vector<int> W) {
n=N;
m=M;
for (int i=0;i<m;i++) {
e.pb(mp(W[i],mp(U[i],V[i])));
}
mst();
}
int getMinimumFuelCapacity(int x, int y) {
int ans=shortest_path(x,y);
if (ans>=INF) return -1;
return ans;
}
