#include<bits/stdc++.h>
using namespace std;
#define F first
#define S second
#include "dreaming.h"
typedef pair<int, int> ii;
typedef vector<ii> vii;
vector<vii> adj;
#define ll long long
vector<bool> vis;
vector<ii> leafdist;
vector<ii> h1, h2;
vector<int> longest;
vector<int> comp;
int component=0;
ii diam(int s, int p=-1, int dist=0){
//cout<<s<<" "<<p<<endl;
vis[s] = true;
ii l = {0, s}, t;
longest[s] = max(longest[s], dist);
comp[s] = component;
for(auto x : adj[s]) if(x.F!=p) t = diam(x.F, s, dist+x.S), l = max(l, ii(x.S + t.F, t.S));
leafdist[s] = l;
return l;
}
int travelTime(int n, int m, int L, int A[], int B[], int T[]) {
adj.assign(n+1, vii());
vis.assign(n+1, false);
leafdist.assign(n+1, ii(0,0));
longest.assign(n+1, 0);
comp.assign(n+1, 0);
for(long long i=0;i<m;i++){
adj[A[i]].push_back(ii(B[i], T[i]));
adj[B[i]].push_back(ii(A[i], T[i]));
}
int ans=0;
int cnt=0;
for(int i=0;i<n;i++){
if(vis[i]) continue;
//cout<<"crap\n";
component = ++cnt;
int root = diam(i).S;
//cout<<"============= "<<root<<" ============\n";
ii root2 = diam(root);
ans = max(ans, root2.F);
diam(root2.S);
// Find center;
}
//cout<<cnt<<endl;
//cout<<comp[0]<<endl;
vii center(cnt, ii(-1000000,1000000));
for(int i=0;i<n;i++){
//cout<<i<<" "<<longest[i]<<endl;
if(-center[comp[i]-1].F>longest[i]) center[comp[i]-1] = ii(-longest[i], i);
}
//for(int i=0;i<center.size();i++) cout<<i<<" "<<center[i].F<<endl;
sort(center.begin(), center.end());
//if(center.size()>=1) ans = max(ans, L);
if(center.size()>=2) ans = max(ans, -center[0].F-center[1].F + L);
if(center.size()>=3) ans = max(ans, -center[2].F-center[1].F + 2*L);
return ans;
}
