#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
#include "dreaming.h"
using namespace std;
typedef long long ll;
int last_node,max_dist;
void dfs(int a,int par,vector<vector<pair<int,int>>>& g,int& d,vector<bool>& seen,vector<pair<int,int>>& p){
seen[a]=true;
for(auto x:g[a]){
if(x.first==par)continue;
d+=x.second;
p[x.first]={a,x.second};
dfs(x.first,a,g,d,seen,p);
d-=x.second;
}
if(d>max_dist){
max_dist=d;
last_node=a;
}
}
int mid(int a,vector<pair<int,int>>& p){
vector<int> path;
int ans=1e9,cnt=0;
while(a!=-1){
path.push_back(p[a].second);
a=p[a].first;
}
for(int i=0;i<path.size();i++){
cnt+=path[i];
ans=min(ans,max(cnt,max_dist-cnt));
}
return ans;
}
int travelTime(int N, int M, int L, int A[], int B[], int T[]) {
vector<vector<pair<int,int>>> g(N,vector<pair<int,int>>());
vector<bool> seen(N,false);
for(int i=0;i<M;i++){
g[A[i]].push_back({B[i],T[i]});
g[B[i]].push_back({A[i],T[i]});
}
vector<int> best;
vector<pair<int,int>>p(N);
int ans=0;
for(int i=0;i<N;i++){
if(!seen[i]){
max_dist=-1;
int di=0;
dfs(i,i,g,di,seen,p);
p[last_node].first=-1;
max_dist=-1;
dfs(last_node,last_node,g,di,seen,p);
ans=max(ans,max_dist);
best.push_back(mid(last_node,p));
}
}
sort(best.rbegin(),best.rend());
if(best.size()>1)ans=max(ans,best[0]+L+best[1]);
for(int i=2;i<best.size();i++){
ans=max(ans,2*L+best[1]+best[i]);
}
//for(int x:best)cout<<x<<' ';
return ans;
}
/*int main(){
int n,m,l;
cin>>n>>m>>l;
int a[m],b[m],t[m];
for(int i=0;i<m;i++)cin>>a[i]>>b[i]>>t[i];
cout<<travelTime(n,m,l,a,b,t);
}*/
