#include<bits/stdc++.h>
using namespace std;
#define pb push_back
#define fi first
#define se second
#define for1(i,j,k) for(int i=j;i<=k;i++)
#define for2(i,j,k) for(int i=j;i>=k;i--)
#define for3(i,j,k,l) for(int i=j;i<=k;i+=l)
#define bit(n,i) ((n>>i)&1)
#define all(x) x.begin(),x.end()
//#pragma GCC optimize("O2,unroll-loops")
//#pragma GCC target("avx,avx2,bmi,bmi2,sse,sse2,sse3,ssse3,sse4,popcnt")
//#define int long long
typedef long long ll;
typedef pair<int,int> pii;
typedef double ld;
typedef pair<ld,ld> pdd;
typedef pair<ll,ll> pll;
const ll maxn=4e5+69;
const ll offset=1e9;
const ll block_sz=317;
const ll inf=1e18;
const ll mod=1e9+7;
int n,par[maxn],m,deg[maxn],val[maxn],up[maxn][20],in[maxn],out[maxn],Time,ans[maxn];
bool ok[maxn];
vector<int> adj[maxn];
pair<int,pii> Edge[maxn];
map<pii,int> L;
int Find(int u)
{
return (par[u]<0?u:par[u]=Find(par[u]));
}
void AddEdge(int u,int v,int w)
{
val[n]=w;
deg[u]++;
deg[v]++;
if (deg[u]>2 || deg[v]>2) ok[n]=1;
u=Find(u);
v=Find(v);
par[n]+=par[u];
par[u]=n;
adj[n].pb(u);
if (u!=v)
{
adj[n].pb(v);
par[n]+=par[v];
par[v]=n;
}
ok[n]=ok[n]|ok[u]|ok[v];
//cerr<<n<<' '<<ok[n]<<' '<<val[n]<< " kk\n";
n++;
}
void dfs(int u,int pre)
{
in[u]=++Time;
up[u][0]=pre;
for1(i,1,19)
{
up[u][i]=up[up[u][i-1]][i-1];
}
if (ok[u]||adj[u].size()==1) ans[u]=val[u];
else if (u!=pre) ans[u]=ans[pre];
else ans[u]=-1;
//cerr <<"acac "<<u<<' '<<ans[u]<<'\n';
for(int v: adj[u])
{
dfs(v,u);
}
out[u]=Time;
}
bool is_ancestor(int u,int v)
{
return (in[u]<=in[v] && out[v] <= out[u]);
}
int lca(int u,int v)
{
if (is_ancestor(u,v)) return u;
if (is_ancestor(v,u)) return v;
for2(i,19,0)
{
if (!is_ancestor(up[u][i],v)) u=up[u][i];
}
return up[u][0];
}
void init(int N,int M,vector<int> U,vector<int> V, vector<int> W)
{
n=N;
m=M;
for1(i,0,n+m) par[i]=-1;
for1(i,0,m-1)
{
Edge[i+1]={W[i],{U[i],V[i]}};
//L[{U[i],V[i]}]=W[i];
}
sort(Edge+1,Edge+1+m);
for1(i,1,m)
{
AddEdge(Edge[i].se.fi,Edge[i].se.se,Edge[i].fi);
}
dfs(n-1,n-1);
}
int getMinimumFuelCapacity(int X, int Y) {
return ans[lca(X,Y)];
}
//
//int main() {
// int N, M;
// assert(2 == scanf("%d %d", &N, &M));
//
// std::vector<int> U(M), V(M), W(M);
// for (int i = 0; i < M; ++i) {
// assert(3 == scanf("%d %d %d", &U[i], &V[i], &W[i]));
// }
//
// int Q;
// assert(1 == scanf("%d", &Q));
//
// std::vector<int> X(Q), Y(Q);
// for (int i = 0; i < Q; ++i) {
// assert(2 == scanf("%d %d", &X[i], &Y[i]));
// }
//
// init(N, M, U, V, W);
//
// std::vector<int> minimum_fuel_capacities(Q);
// for (int i = 0; i < Q; ++i) {
// minimum_fuel_capacities[i] = getMinimumFuelCapacity(X[i], Y[i]);
// }
//
// for (int i = 0; i < Q; ++i) {
// printf("%d\n", minimum_fuel_capacities[i]);
// }
//
// return 0;
//}
