#include "dreaming.h"
using namespace std;
#include <iostream>
#include <vector>
#include <algorithm>
long long maxjos[100005];
long long max2jos[100005];
long long canjos[100005];
vector<int>vec;
vector<pair<int,int> >adj[100005];
int dist[100005][5];
int fre[100005];
void dfs(int curr,int par)
{
vec.push_back(curr);
for(auto k:adj[curr])
{
if(k.first!=par)
{
fre[k.first]=1;
dfs(k.first,curr);
}
}
}
void updatedist(int curr,int par,int iter)
{
for(auto k:adj[curr])
{
if(k.first!=par)
{
dist[k.first][iter]=dist[curr][iter]+k.second;
updatedist(k.first,curr,iter);
}
}
}
int travelTime(int N, int M, int L, int A[], int B[], int T[])
{
for(int i=0; i<M; i++)
{
adj[A[i]].push_back({B[i],T[i]});
adj[B[i]].push_back({A[i],T[i]});
}
int n=N;
vector<int>ans;
for(int i=0; i<n; i++)
{
if(fre[i]==0)
{
vec.clear();
fre[i]=1;
dfs(i,-1);
updatedist(i,-1,0);
int maxim=vec[0],maxim2=vec[0];
for(auto k:vec)
{
if(dist[k][0]>=dist[maxim][0])
{
maxim=k;
}
}
updatedist(maxim,-1,1);
for(auto k:vec)
{
if(dist[k][1]>=dist[maxim2][1])
{
maxim2=k;
}
}
updatedist(maxim2,-1,2);
int rez=1000000006;
for(auto k:vec)
{
rez=min(rez,max(dist[k][2],dist[k][1]));
}
ans.push_back(rez);
}
}
sort(ans.begin(),ans.end());
reverse(ans.begin(),ans.end());
int sol=ans[0];
if(ans.size()>=2)
{
sol=max(sol,ans[0]+ans[1]+L);
}
if(ans.size()>=3)
{
sol=max(sol,ans[2]+ans[1]+2*L);
}
return sol;
}
