#include "dreaming.h"
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int n,m,l,used[131072],p1;
pair <int,int> parent[131072];
vector <pair <int,int>> v[131072];
vector <int> edges;
int mx=0,p;
void dfs(int beg,int par,int dist)
{
used[beg]=1;
if(mx<dist)
{
mx=dist;
p=beg;
}
for(auto nb:v[beg])
{
if(!used[nb.first])dfs(nb.first,beg,dist+nb.second);
}
}
void dfs1(int beg,int par,int dist,int last)
{
if(mx<dist)
{
mx=dist;
p1=beg;
}
parent[beg]={par,last};
for(auto nb:v[beg])
{
if(nb.first!=par)dfs1(nb.first,beg,dist+nb.second,nb.second);
}
}
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++)
{
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])
{
mx=0;
dfs(0,-1,0);
mx=0;
dfs1(p,-1,0,0);
int x=p1,mn=mx,d=0;
while(x!=p)
{
mn=min(mn,max(d,mx-d));
d+=parent[x].second;
x=parent[x].first;
}
edges.push_back(mn);
}
}
sort(edges.rbegin(),edges.rend());
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);
}
}
