#include <bits/stdc++.h>
#include "dreaming.h"
using namespace std;
#define pii pair<int,int>
#define piii pair<int,pii>
#define MAXN 100000
#define ll long long int
#define pil pair<int,ll>
vector<pii> adj[MAXN];
bool vis[MAXN];
int dist[MAXN], dist2[MAXN];
int last[MAXN];
queue<int> q;
pii furthest (int n){
pii ans = {0,0};
dist[n] = 0;
last[n] = -1;
q.push(n);
while (!q.empty()) {
int cur = q.front();
q.pop();
for (pii p : adj[cur]) if (dist[p.first] == -1) {
dist[p.first] = dist[cur] + p.second;
last[p.first] = cur;
if (dist[p.first] > ans.second) {
ans.second = dist[p.first];
ans.first = p.first;
}
q.push(p.first);
}
}
return ans;
}
int far (int n) {
q.push(n);
int cur = 0, best=0,ans=0;
dist2[n] = 0;
while (!q.empty()) {
cur = q.front();
if (dist2[cur] > best) {
best = dist2[cur];
ans = cur;
}
vis[cur] = true;
q.pop();
for (pii p : adj[cur]) if (!vis[p.first]) {
q.push(p.first);
dist2[p.first] = dist2[cur] + p.second;
}
}
return ans;
}
int travelTime (int N, int M, int L, int A[], int B[], int T[]) {
memset(dist,-1,sizeof(dist));
memset(vis,0,sizeof(vis));
for (int x = 0; x < M; x++) {
adj[A[x]].push_back({B[x],T[x]});
adj[B[x]].push_back({A[x],T[x]});
}
int components = 0;
int max1 = 0, max2 = 0, max3 = 0,maxdiam = 0;
for (int x = 0; x < N; x++) if (!vis[x]) {
components++;
if(!adj[x].size()) continue;
pii diameter = furthest(far(x));
int cur = diameter.first;
int dista = diameter.second, radiusish = dista/2, radius = 0;
maxdiam = max(maxdiam,dista);
while (dist[last[cur]] > radiusish) cur = last[cur];
radius = min(max(dist[cur],dista-dist[cur]),max(dist[last[cur]],dista-dist[last[cur]]));
if (radius >= max1) {
max3 = max2;
max2 = max1;
max1 = radius;
}
else if (radius >= max2) {
max3 = max2;
max2 = radius;
}
else if (radius > max3) max3 = radius;
}
if (components == 1) return maxdiam;
if (components == 2) return max(max1+max2+L,maxdiam);
return max(max1+max2+L,max(maxdiam,max2+max3+L*2));
}
