#include "dreaming.h"
#include <bits/stdc++.h>
using namespace std;
#define pii pair<int, int>
#define F first
#define S second
#define emb emplace_back
#define em emplace
const int maxn = 1e5 + 5;
const int inf = 2e9;
vector<pii> adj[maxn];
bool vis[maxn], curv[maxn];
int pa[maxn], dist[maxn];
int mxx = -inf;
queue<pii> qu;
vector<int> cen;
int travelTime(int n, int m, int l, int a[], int b[], int t[]){
for(int i=0;i<m;++i){
int u = a[i], v = b[i], w = t[i];
adj[u].emb(w, v);
adj[v].emb(w, u);
}
memset(pa, -1, sizeof(pa));
for(int i=0;i<n;++i){
if(vis[i]) continue;
qu.em(0, i);
curv[i] = 1;
int d1, d2, mx = -inf;
while(!qu.empty()){
auto [w, u] = qu.front();
qu.pop();
if(mx < w){
mx = w;
d1 = u;
}
for(auto [vw, v] : adj[u]){
if(!curv[v]){
qu.em(w + vw, v);
curv[v] = 1;
}
}
}
qu.em(0, d1);
vis[d1] = 1, mx = -inf;
while(!qu.empty()){
auto [w, u] = qu.front();
qu.pop();
if(mx < w){
mx = w;
d2 = u;
}
for(auto [vw, v] : adj[u]){
if(!vis[v]){
qu.em(w + vw, v);
vis[v] = 1;
pa[v] = u;
dist[v] = vw;
}
}
}
int nw = 0, mn = inf, c = 0;
while(d2 != -1){
int d = abs(nw + nw - mx);
if(mn > d){
mn = d;
c = max(nw, mx - nw);
}
nw += dist[d2];
d2 = pa[d2];
}
mxx = max(mx, mxx);
cen.emb(c);
}
sort(cen.begin(), cen.end(), greater<int>());
if(cen.size() >= 2) mxx = max(mxx, cen[0] + cen[1] + l);
if(cen.size() >= 3) mxx = max(mxx, cen[1] + cen[2] + l*2);
return mxx;
}
