#include "dreaming.h"
#include <bits/stdc++.h>
using namespace std;
#define type(x) __typeof((x).begin())
#define foreach(it, x) for(type(x) it = (x).begin(); it != (x).end(); it++)
typedef long long ll;
typedef pair < int, int > ii;
const int inf = 1e9 + 333;
const ll linf = 1e18 + inf;
const int N = 1e5 + 5;
int curRoot;
vector < ii > v[N];
bool h[N];
int mx;
int dist[N], root[N];
vector < int > vec;
void dfs(int p, int x, int t = 0) {
root[x] = curRoot;
vec.push_back(x);
h[x] = 1;
dist[x] = t;
if(mx == -1 or t > dist[mx]) {
mx = x;
}
foreach(it, v[x]) {
int u = it -> first;
int e = it -> second;
if(u != p)
dfs(x, u, t + e);
}
}
int distA[N], distB[N];
int calcLp(int x) {
mx = -1;
vec.clear();
dfs(-1, x);
//printf("mx = %d\n", mx);
//////////////////////////////
int A = mx;
mx = -1;
vec.clear();
dfs(-1, A);
foreach(it, vec) {
int x = *it;
distA[x] = dist[x];
}
/////////////////////////////
int B = mx;
mx = -1;
vec.clear();
dfs(-1, B);
foreach(it, vec) {
int x = *it;
distB[x] = dist[x];
}
int mn = 2 * inf, mni = -1;
foreach(it, vec) {
int x = *it;
//printf("x = %d\n", x);
if(abs(distA[x] - distB[x]) < mn) {
mn = abs(distA[x] - distB[x]);
mni = x;
}
}
//puts("");
assert(mni != -1);
return mni;
}
int f(int x) {
if(x != root[x])
return root[x] = f(root[x]);
return x;
}
int travelTime(int n, int m, int l, int A[], int B[], int T[]) {
for(int i = 0; i < m; i++) {
int x = A[i];
int y = B[i];
int c = T[i];
v[x].push_back(ii(y, c));
v[y].push_back(ii(x, c));
}
int found = -1;
vector < ii > vec;
for(int i = 0; i < n; i++) {
if(!h[i]) {
//printf("i = %d\n", i);
curRoot = i;
int x = calcLp(i);
int a = distA[x];
int b = distB[x];
if(a < b)
swap(a, b);
//printf("a = %d b = %d\n", a, b);
vec.push_back(ii(a, b));
}
}
sort(vec.begin(), vec.end());
if(vec.size() == 1) {
return vec[0].first + vec[0].second;
}
else if(vec.size() == 2){
return max(vec[1].first + vec[1].second, vec[0].first + vec[1].first + l);
}
else {
int mx = vec.back().first + vec.back().second;
mx = max(mx, vec[vec.size() - 1].first + vec[vec.size() - 2].first + l);
mx = max(mx, vec[vec.size() - 2].first + vec[vec.size() - 3].first + 2 * l);
return mx;
}
}
