#include "dreaming.h"
#include <iostream>
#include <vector>
#include <algorithm>
#include <cstring>
using namespace std;
int n,m,l,used[131072],dp[131072][2];
pair <int,int> opt[131072][2];
vector <pair <int,int>> v[131072];
vector <int> edges;
int mn=1e9;
void dfs(int beg,int par)
{
used[beg]=1;
vector <pair <int,int>> v1;
for(auto nb:v[beg])
{
if(!used[nb.first])
{
dfs(nb.first,beg);
v1.push_back({dp[nb.first][0]+nb.second,nb.first});
}
}
sort(v1.rbegin(),v1.rend());
if(v1.size())
{
dp[beg][0]=v1[0].first;
opt[beg][0]=v1[0];
if(v1.size()>1)opt[beg][1]=v1[1];
}
}
void dfs1(int beg,int par,int la)
{
if(par!=-1)
{
dp[beg][1]=dp[par][1]+la;
if(opt[par][0].second==beg)dp[beg][1]=max(dp[beg][1],opt[par][1].first+la);
else dp[beg][1]=max(dp[beg][1],opt[par][0].first+la);
}
mn=min(mn,max(dp[beg][0],dp[beg][1]));
for(auto nb:v[beg])
{
if(nb.first!=par)dfs1(nb.first,beg,nb.second);
}
}
int travelTime(int N, int M, int L, int A[], int B[], int T[])
{
n=N;
m=M;
l=L;
memset(dp,0,sizeof(dp));
memset(used,0,sizeof(used));
memset(opt,0,sizeof(opt));
edges.clear();
for(int i=0;i<n;i++)v[i].clear();
for(int i=0;i<m;i++)
{
v[A[i]].push_back({B[i],T[i]});
v[B[i]].push_back({A[i],T[i]});
}
for(int i=0;i<n;i++)
{
if(!used[i])
{
dfs(i,-1);
mn=1e9;
dfs1(i,-1,0);
//cout<<mx<<" "<<mn<<" "<<i<<endl;
edges.push_back(mn);
//cout<<i<<" "<<mn<<endl;
}
}
//for(int i=0;i<n;i++)cout<<dp[i][0]<<" "<<dp[i][1]<<" "<<i<<endl;
sort(edges.rbegin(),edges.rend());
/*for(auto i:edges)cout<<i<<" ";
cout<<endl;*/
if(edges.size()==1)return edges[0];
else
{
if(edges.size()==2)return edges[0]+edges[1]+l;
else return max(edges[0]+edges[1]+l,edges[1]+edges[2]+2*l);
}
}
