#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);
}
for(int i=0;i<n;++i){
if(vis[i]) continue;
qu.em(0, i);
memset(curv, 0, sizeof(curv));
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;
memset(pa, -1, sizeof(pa));
memset(dist, 0, sizeof(dist));
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, curr = d2, mn = inf, c = 0;
while(d2 != -1){
nw += dist[d2];
int d = abs(nw + nw - mx);
if(mn > d){
mn = d;
c = max(nw, mx - nw);
}
d2 = pa[d2];
}
mxx = max(mx, mxx);
cen.emb(c);
}
int arr[3] = {-inf, -inf, -inf};
for(auto e : cen){
arr[2] = max(arr[2], e);
if(arr[2] > arr[1]) swap(arr[1], arr[2]);
if(arr[1] > arr[0]) swap(arr[0], arr[1]);
}
return max(mxx, max(arr[0] + arr[1], arr[1] + arr[2] + l) + l);
}
