#include <bits/stdc++.h>
#define MAX 100005
#include "dreaming.h"
using namespace std;
struct str
{
int dist;
int where;
}Longest[MAX];
int LongestRev[MAX];
struct str2
{
int node;
int len;
};
vector<str2>tree[MAX];
int n,m,l;
bool visited[MAX];
int parent[MAX];
int dpar[MAX];
int root[MAX];
int diam[MAX];
void find_longest(int node,int rt)
{
root[node]=rt;
visited[node]=1;
for(auto structure : tree[node])
{
int son=structure.node;
int len=structure.len;
if(!visited[son])
{
parent[son]=node;
dpar[son]=len;
find_longest(son,rt);
if(Longest[node].dist<Longest[son].dist+len)
{
Longest[node].dist=Longest[son].dist+len;
Longest[node].where=son;
}
}
}
if(!Longest[node].dist)
Longest[node].where=node;
}
void debug_longest()
{
int i;
for(i=1;i<=n;++i)
cout<<Longest[i].dist<<' '<<Longest[i].where<<'\n';
}
void init_Longest()
{
int i;
for(i=1;i<=n;++i)
if(!visited[i])
find_longest(i,i);
for(i=1;i<=n;++i)
visited[i]=0;
}
void find_longest_rev(int node)
{
visited[node]=1;
LongestRev[node]=max(LongestRev[node],LongestRev[parent[node]]+dpar[node]);
int max1=0,max2=0;
for(auto structure : tree[node])
{
int son=structure.node;
int len=structure.len;
if(son!=parent[node])
{
if(max1<Longest[son].dist+len)
{
max2=max1;
max1=Longest[son].dist+len;
}
else
if(max2<Longest[son].dist+len)
max2=Longest[son].dist+len;
}
}
for(auto structure : tree[node])
{
int son=structure.node;
int len=structure.len;
if(son!=parent[node])
{
if(Longest[son].dist+len==max1)
LongestRev[son]=max2+len;
else
LongestRev[son]=max1+len;
find_longest_rev(son);
}
}
}
void init_Longest_rev()
{
int i;
for(i=1;i<=n;++i)
if(!visited[i])
find_longest_rev(i);
for(i=1;i<=n;++i)
visited[i]=0;
}
void debug_longest_rev()
{
int i;
for(i=1;i<=n;++i)
cout<<LongestRev[i]<<' ';
}
void find_optimal(int node,int& answer)
{
if(visited[node])
return;
visited[node]=1;
answer=min(answer,max(Longest[node].dist,LongestRev[node]));
if(Longest[node].dist>LongestRev[node])
find_optimal(Longest[node].where,answer);
else
find_optimal(parent[node],answer);
}
void diameter()
{
int i;
for(i=1;i<=n;++i)
{
int rt=root[i];
diam[rt]=max(diam[rt],max(Longest[i].dist,LongestRev[i]));
}
}
int init_opt()
{
int max1=-1e9,max2=-1e9,max3=-1e9;
int maxim=0;
int i;
for(i=1;i<=n;++i)
if(!visited[root[i]])
{
maxim=max(maxim,diam[root[i]]);
int answer=2e9;
find_optimal(i,answer);
if(answer>max1)
{
max3=max2;
max2=max1;
max1=answer;
}
else
if(answer>max2)
{
max3=max2;
max2=answer;
}
else
if(answer>max3)
max3=answer;
}
return max(maxim,max(max1+max2+l,max2+max3+2*l));
}
int travelTime(int N,int M,int L,int A[],int B[],int T[]){
n=N;
m=M;
l=L;
int i;
for(i=0;i<m;++i)
{
int node1,node2,len;
node1=A[i];
node2=B[i];
len=T[i];
++node1;
++node2;
tree[node1].push_back({node2,len});
tree[node2].push_back({node1,len});
}
init_Longest();
init_Longest_rev();
diameter();
return init_opt();
}
