#include <iostream>
#include <algorithm>
#include <vector>
#include "dreaming.h"
using namespace std;
const int N=2e5+5;
int n,m;
long long l;
vector<pair<int,int>>adj[N];
long long ans=0;
long long sub[N],best[N][3],unde[N][2];
bool viz[N];
int A[N],B[N],T[N];
void dfs(int nod,int p)
{
viz[nod]=true;
for(auto [u,c]:adj[nod])
{
if(u!=p)
{
dfs(u,nod);
if(best[nod][1]<sub[u]+c)
{
if(best[nod][1]>best[nod][2])
{
best[nod][2]=best[nod][1];
unde[nod][2]=unde[nod][1];
}
best[nod][1]=sub[u]+c;
unde[nod][1]=u;
}
else
if(best[nod][2]<sub[u]+c)
{
best[nod][2]=sub[u]+c;
unde[nod][2]=u;
}
}
}
sub[nod]=best[nod][1];
ans=max(best[nod][1]+best[nod][2],ans);
}
long long rate=1e10;
void dfs2(int nod,int p,int cost)
{
viz[nod]=true;
if(p!=0)
{
if(unde[p][1]!=nod)
{
if(best[p][1]+cost>best[nod][1])
{
best[nod][2]=best[nod][1];
unde[nod][2]=unde[nod][1];
best[nod][1]=best[p][1]+cost;
unde[nod][1]=p;
}
else
if(best[p][1]+cost>best[nod][2])
{
best[nod][2]=best[p][1]+cost;
unde[nod][2]=p;
}
}
else
if(unde[p][2]!=nod)
{
if(best[p][2]+cost>best[nod][1])
{
best[nod][2]=best[nod][1];
unde[nod][2]=unde[nod][1];
best[nod][1]=best[p][2]+cost;
unde[nod][1]=p;
}
else
if(best[p][2]+cost>best[nod][2])
{
best[nod][2]=best[p][2]+cost;
unde[nod][2]=p;
}
}
}
rate=min(rate,max(best[nod][1],best[nod][2]));
for(auto [u,c]:adj[nod])
{
if(u!=p)
{
dfs2(u,nod,c);
}
}
}
int travelTime(int N,int M,int L,int A[],int B[],int T[])
{
n=N,m=M,l=L;
for(int i=0;i<m;i++)
{
int a=A[i],b=B[i];
long long c=T[i];
a++,b++;
adj[a].push_back({b,c});
adj[b].push_back({a,c});
}
for(int i=1;i<=n;i++)
{
if(viz[i]==false)
{
dfs(i,0);
}
}
for(int i=1;i<=n;i++)
viz[i]=false;
vector<long long>to_do;
for(int i=1;i<=n;i++)
{
if(viz[i]==false)
{
dfs2(i,0,0);
to_do.push_back(rate);
rate=1e10;
}
}
sort(to_do.begin(),to_do.end());
if(to_do.size()==1)
return ans;
if(to_do.size()==2)
{
return max(ans,to_do[0]+to_do[1]+l);
}
long long a=to_do.back();
to_do.pop_back();
long long b=to_do.back();
to_do.pop_back();
long long c=to_do.back();
ans=max(ans,a+b+l);
ans=max(ans,b+c+2*l);
return ans;
}
/*int main()
{
cin>>n>>m>>l;
for(int i=0;i<m;i++)
cin>>A[i];
for(int i=0;i<m;i++)
cin>>B[i];
for(int i=0;i<m;i++)
cin>>T[i];
cout<<travel_time(n,m,l,A,B,T);
return 0;
}*/
