#include "dreaming.h"
#include <vector>
#include <algorithm>
#include <cstdio>
using namespace std;
int cen;
int ans=0;
struct ei {
int vec,wgt;
};
vector<ei> pth[100100];
bool visit[100100];
int mx[100100];
int smx[100100];
int survey(int x,int p) {
visit[x]=true;
int cur;
for (auto &i:pth[x]) {
if (i.vec==p) continue;
cur=i.wgt+survey(i.vec,x);
if (cur>=mx[x]) {
smx[x]=mx[x];
mx[x]=cur;
} else if (cur>smx[x]) {
smx[x]=cur;
}
}
return mx[x];
}
void findcen(int x,int p,int dis) {
if (dis>=mx[x]) {
smx[x]=mx[x];
mx[x]=dis;
} else if (dis>smx[x]) {
smx[x]=dis;
}
ans=max(ans,smx[x]+mx[x]);
cen=min(cen,mx[x]);
for (auto &i:pth[x]) {
if (i.vec==p) continue;
if (i.wgt+mx[i.vec]==mx[x]) {
findcen(i.vec,x,smx[x]+i.wgt);
} else {
findcen(i.vec,x,mx[x]+i.wgt);
}
}
}
int travelTime(int N, int M, int L, int A[], int B[], int T[]) {
for (int i=0;i<M;i++) {
pth[A[i]].push_back(ei{B[i],T[i]});
pth[B[i]].push_back(ei{A[i],T[i]});
}
vector<int> cens;
for (int i=0;i<N;i++) {
if (visit[i]) continue;
survey(i,i);
cen=1e9;
findcen(i,i,0);
cens.push_back(cen);
}
sort(cens.begin(),cens.end(),[](int &a, int &b) {
return a>b;
});
if (cens.size()>1) ans=max(ans,cens[0]+cens[1]+L);
if (cens.size()>2) ans=max(ans,cens[1]+cens[2]+2*L);
return ans;
}
