#include "dreaming.h"
#include <bits/stdc++.h>
using namespace std;
const int N=1e5+4;
vector<array<int,2>>adj[N];
int d[N][2],vis[N],wd;
vector<int>comp;
void build(int u,int p){
comp.push_back(u);
for(auto&[v,w]:adj[u]){
if(!(v^p))
continue;
build(v,u);
}
}
void unq(vector<int>&v){
sort(v.begin(),v.end());
v.erase(unique(v.begin(),v.end()),v.end());
}
void dfs(int u,bool x){
vis[u]=1;
for(auto&[v,w]:adj[u]){
if(vis[v])
continue;
d[v][x]=d[u][x]+w;
dfs(v,x);
}
}
int findmxlen(int node){
comp.clear();
build(node,0);
unq(comp);
d[node][0]=0;
dfs(node,0);
int mx=-1,kraj1,kraj2;
for(int u:comp){
if(d[u][0]>mx){
mx=d[u][0];
kraj1=u;
}
vis[u]=0;
}
d[kraj1][0]=0;
dfs(kraj1,0);
mx=-1;
for(int u:comp){
if(d[u][0]>mx){
mx=d[u][0];
kraj2=u;
}
vis[u]=0;
}
d[kraj2][1]=0;
dfs(kraj2,1);
int ret=1e9;
for(int u:comp){
ret=min(ret,max(d[u][0],d[u][1]));
vis[u]=1;
}
wd=max(wd,d[kraj2][0]);
return ret;
}
int travelTime(int N, int M, int L, int A[], int B[], int T[]) {
int n=N,m=M,l=L;
for(int i=0,u,v,w;i<m;++i){
u=A[i];
v=B[i];
w=T[i];
++u,++v;
adj[u].push_back({v,w});
adj[v].push_back({u,w});
}
fill(vis,vis+n+2,0);
vector<int>poludijametri;
for(int i=1;i<=n;++i){
if(vis[i])
continue;
poludijametri.push_back(findmxlen(i));
}
sort(poludijametri.rbegin(),poludijametri.rend());
int ans=wd;
if(poludijametri.size()>1)
ans=max(ans,poludijametri[0]+poludijametri[1]+l);
if(poludijametri.size()>2)
ans=max(ans,poludijametri[1]+poludijametri[2]+2*l);
return ans;
}
