#include <bits/stdc++.h>
#include "dreaming.h"
#define MAXN 100010
using namespace std;
vector<pair<int,int> > G[MAXN];
bool V[MAXN];
int maxx=0,cur,cnt[MAXN],ans=0;
vector<pair<int,int> > dist,v;
void DFS_Diameter(int i,int p,int d)
{
V[i]=true;
if (d>=maxx)
{
maxx=d;
cur=i;
}
for (auto next : G[i])
{
if (next.first!=p)
DFS_Diameter(next.first,i,d+next.second);
}
}
void DFS_Distances(int i,int p,int d)
{
dist.push_back({d,i});
for (auto next : G[i])
{
if (next.first!=p)
DFS_Distances(next.first,i,d+next.second);
}
}
int travelTime(int N, int M, int L, int A[], int B[], int T[])
{
for (int i=0;i<M;i++)
{
G[A[i]].push_back({B[i],T[i]});
G[B[i]].push_back({A[i],T[i]});
}
for (int i=0;i<N;i++)
{
if (!V[i])
{
int a=i,b=i;
DFS_Diameter(i,i,0);
a=cur;
maxx=0;
DFS_Diameter(a,a,0);
b=cur;
maxx=0;
dist.clear();
DFS_Distances(a,a,0);
DFS_Distances(b,b,0);
sort(dist.begin(),dist.end());
for (auto x : dist)
{
cnt[x.second]++;
if (cnt[x.second]==2)
{
v.push_back(x);
break;
}
}
}
}
sort(v.begin(),v.end());
for (int i=0;i<v.size()-1;i++)
{
G[v[v.size()-1].second].push_back({v[i].second,L});
G[v[i].second].push_back({v[v.size()-1].second,L});
}
DFS_Diameter(0,0,0);
DFS_Diameter(cur,cur,0);
return maxx;
}
