#include <bits/stdc++.h>
#include <dreaming.h>
using namespace std;
typedef pair<int,int> ii;
typedef vector<ii> vii;
typedef vector<int> vi;
int n,m,l,a[100000],b[100000],t[100000];
int gp[100000],dp[100000];
bool vis[100000];
vii adj[100000];
vi gap,gru;
void dfs1(int v,int f){
for(auto [u,w] : adj[v]){
if(u == f) continue;
dfs1(u,v);
dp[v] = max(dp[u]+w,dp[v]);
}
}
void dfs2(int v,int f){
gru.push_back(v);
multiset<int> s;
for(auto [u,w] : adj[v]){
if(u == f) continue;
s.insert(dp[u]+w);
}
for(auto [u,w] : adj[v]){
if(u == f) continue;
s.erase(s.find(dp[u]+w));
int vl;
if(!s.empty()){
auto it = s.end(); it--;
vl = *it;
}
else
vl = 0;
gp[u] = max(gp[v]+w,vl+w);
s.insert(dp[u]+w);
}
for(auto [u,w] : adj[v]){
if(u == f) continue;
dfs2(u,v);
}
}
int travelTime(int N,int M,int L,int A[],int B[],int T[]){
int ans = 0;
n = N, m = M, l = L;
for(int i = 0; i < m; ++i)
a[i] = A[i], b[i] = B[i], t[i] = T[i];
// cin >> n >> m >> l;
// for(int i = 0; i < m; ++i)
// cin >> a[i] >> b[i] >> t[i];
if(n == 1) return 0;
for(int i = 0; i < m; ++i){
adj[a[i]].push_back({b[i],t[i]});
adj[b[i]].push_back({a[i],t[i]});
}
for(int i = 0; i < n; ++i){
if(vis[i])
continue;
dp[i] = 0, gp[i] = 0;
dfs1(i,-1);
dfs2(i,-1);
int mn = dp[i]+gp[i];
for(auto it : gru)
ans = max(dp[it]+gp[it],ans), mn = min(max(dp[it],gp[it]),mn), vis[it] = 1;
// cout << i << endl;
// for(auto it : gru){
// cout << it << " " << dp[it] << " " << gp[it] << endl;
// }
// cout << mn << " d" << endl;
gru.clear();
gap.push_back(mn);
// break;
}
sort(gap.rbegin(),gap.rend());
if((int) gap.size() >= 2) ans = max(ans,gap[0]+gap[1]+l);
if((int) gap.size() >= 3) ans = max(ans,gap[1]+gap[2]+l+l);
return ans;
}
// int main(){
// int ldq1[2],ldq2[2],ldq3[3];
// cout << travelTime(0,0,0,ldq1,ldq2,ldq3) << endl;
// return 0;
// }
