#include "dreaming.h"
#include <bits/stdc++.h>
using namespace std;
using ll=long long;
vector<vector<pair<int, ll>>> al(100005);
vector<tuple<ll, int, ll>> dist(100005, {1e12, -1, 0});
// dist, previous node, previous edge weight
vector<int> curtree;
vector<ll> guys;
vector<bool> vis(100005);
void dfs(int cur, pair<int,ll> pre){
curtree.push_back(cur);
for(auto [to, cost]:al[cur]){
//~ printf("at %d, to %d, cost %d\n", cur, to, cost);
if(to==pre.first)continue;
get<0>(dist[to])=get<0>(dist[cur])+cost;
get<1>(dist[to])=cur;
get<2>(dist[to])=cost;
dfs(to, {cur, cost});
}
}
int travelTime(int N, int M, int L, int A[], int B[], int T[]) {
for(int i=0;i<M;i++){
al[A[i]].push_back({B[i], T[i]});
al[B[i]].push_back({A[i],T[i]});
}
int x, y;
ll ans=0;
for(int i=0;i<N;i++){
if(vis[i])continue;
dist[i]={0, -1, 0};
dfs(i, {-1, 0});
x=i;
for(auto node : curtree){
if(get<0>(dist[node])>get<0>(dist[x])){
x=node;
}
}
for(auto node : curtree){
dist[node]={1e12, -1, 0};
}
curtree.clear();
dist[x]={0, -1, 0};
dfs(x, {-1, 0});
y=x;
for(auto node : curtree){
if(get<0>(dist[node])>get<0>(dist[y])){
y=node;
}
vis[node]=true;
}
curtree.clear();
ll dl=get<0>(dist[y]);
ans=max(ans, dl);
vector<pair<int,int>> dia;
int cur=y;
ll cv=dl, sm=0;
while(get<1>(dist[cur]) != -1){
sm+=get<2>(dist[cur]);
cv=min(cv, max(dl-sm, sm));
cur=get<1>(dist[cur]);
}
//~ printf("i=%d, x %d, y %d, dl is %d, cv is %d\n",i,x,y,dl, cv);
guys.push_back(cv);
}
sort(guys.begin(),guys.end(), greater<ll>());
assert((int)guys.size() >= 2);
return max({ans, guys[0]+L+guys[1], ((int)guys.size() >= 3? guys[1]+2*L+guys[2]:0));
}
