#include "dreaming.h"
#include <bits/stdc++.h>
using namespace std;
int n, m;
int dis[100000][3];
vector < pair<int, int> > cmp;
queue < pair<int, int> > q;
vector <int> path;
vector < pair<int, int> > v[100000];
int FindFarthest(int s, int z)
{
int ret = s;
q.push({s, 0});
while(q.size())
{
int a = q.front().first;
int d = q.front().second;
q.pop();
if(dis[a][z] != -1)
continue;
dis[a][z] = d;
if(dis[ret][z] < dis[a][z])
ret = a;
for(auto i : v[a])
if(dis[i.first][z] == -1)
q.push({i.first, d + i.second});
}
return ret;
}
int FindCenter(int s)
{
int f1 = FindFarthest(s, 0);
int f2 = FindFarthest(f1, 1);
int k = f2;
path.clear();
while(k != f1)
{
path.push_back(k);
for(auto i : v[k])
if(dis[i.first][1] + i.second == dis[k][1])
{
k = i.first;
break;
}
}
path.push_back(f1);
int r = 0, pn = path.size(), d = dis[f2][1], delta = d;
for(int i = 1; i < pn; i++)
{
int d2 = dis[path[i]][1];
int delta2 = max(d - d2, d2) - min(d - d2, d2);
if(delta > delta2)
{
delta = delta2;
r = i;
}
}
int ret = path[r];
return ret;
}
int travelTime(int N, int M, int L, int A[], int B[], int T[])
{
n = N;
m = M;
for(int i = 0; i < n; i++)
dis[i][0] = dis[i][1] = dis[i][2] = -1;
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]});
}
/*
cout<<"graph"<<endl;
for(int i = 0; i < n; i++)
{
cout<<i<<": ";
for(auto j : v[i])
cout<<"{"<<j.first<<", "<<j.second<<"}, ";
cout<<endl;
}
*/
int h = 0, cn = 0;
for(int i = 0; i < n; i++)
{
if(dis[i][0] != -1)
continue;
int center = FindCenter(i);
int farthest = FindFarthest(center, 2);
cmp.push_back({center, dis[farthest][2]});
if(cmp[h].second < cmp[cn].second)
h = cn;
cn++;
}
/*
cout<<"cmp"<<endl;
for(auto i : cmp)
cout<<i.first<<" "<<i.second<<endl;
*/
int x = cmp[h].first;
for(int i = 0; i < cn; i++)
{
if(i == h)
continue;
v[cmp[i].first].push_back({x, L});
v[x].push_back({cmp[i].first, L});
}
for(int i = 0; i < n; i++)
dis[i][0] = dis[i][1] = dis[i][2] = -1;
int f1 = FindFarthest(0, 0);
int f2 = FindFarthest(f1, 1);
int res = dis[f2][1];
return res;
}
