#include "dreaming.h"
#include <bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define pb push_back
#define ll long long
#define ld long double
const int N=1e5+50;
int n,m,L;
vector<pair<int,int>>E[N];
map<pair<int,int>,int>edge;
int maksdepth,makscvor,par[N];
int komp[N],cnt;
void DFS(int u,int parent,int depth){
par[u]=parent;
if(maksdepth<=depth) makscvor=u;
maksdepth=max(maksdepth,depth);
komp[u]=cnt;
for(auto [i,x]:E[u]){
if(i==parent) continue;
DFS(i,u,depth+x);
}
}
int travelTime(int n1, int m1, int L1, int A[], int B[], int T[]) {
n=n1,m=m1,L=L1;
for(int i=0;i<m;i++){
E[A[i]].pb({B[i],T[i]});
E[B[i]].pb({A[i],T[i]});
edge[{A[i],B[i]}]=edge[{B[i],A[i]}]=T[i];
}
vector<pair<int,int>>a;
for(int i=0;i<n;i++){
//printf("%i\n",i);
if(komp[i]) continue;
cnt++;
maksdepth=makscvor=-1;
DFS(i,-1,0);
int u=makscvor;
maksdepth=makscvor=-1;
DFS(u,-1,0);
int v=makscvor,d=maksdepth,d1=0;
int val=1e9;
while(v!=-1){
val=min(val,max(d,d1));
int x=edge[{v,par[v]}];
d-=x,d1+=x;
v=par[v];
}
a.pb({maksdepth,val});
}
//for(int i=0;i<n;i++) printf("%i: %i\n",i,komp[i]);
//for(auto [u,v]:a) printf("%i %i\n",u,v);
sort(a.begin(),a.end());
for(int i=0;i+1<a.size();i++){
pair<int,int>x=a[i],y=a.back();
if(x.se+y.se+L>y.fi){
a.back().fi=x.se+y.se+L;
a.back().se=min(max(x.se+L,y.se),max(x.se,y.se+L));
}
}
return a.back().fi;
}
