#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(0, x);
//printf("mx = %d\n", mx);
//////////////////////////////
int A = mx;
mx = -1;
vec.clear();
dfs(0, A);
foreach(it, vec) {
int x = *it;
distA[x] = dist[x];
}
/////////////////////////////
int B = mx;
mx = -1;
vec.clear();
dfs(0, 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));
}
priority_queue < ii > Q;
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("x = %d a = %d b = %d\n", x, a, b);
Q.push(ii(-a, -b));
}
}
while(Q.size() > 1) {
int x1 = -Q.top().first;
int y1 = -Q.top().second;
Q.pop();
int x2 = -Q.top().first;
int y2 = -Q.top().second;
Q.pop();
if(x1 + y1 > x1 + x2 + l) {
Q.push(ii(-(x1), -(y1)));
}
else if(x2 + y2 > x1 + x2 + l) {
Q.push(ii(-(x2), -(y2)));
}
else {
int n1 = max(x1, x2);
int n2 = min(x1, x2) + l;
if(n1 < n2)
swap(n1, n2);
Q.push(ii(-(n1), -(n2)));
}
}
return -(Q.top().first + Q.top().second);
}
