#include "dreaming.h"
#include<bits/stdc++.h>
using namespace std;
vector<pair<long long int, long long int>> adj[100005];
long long int proc[100005], no, nod, dist[100005][2];
void dfs(long long int i, long long int p, long long int d) {
if (d > nod) {
no = i, nod = d;
}
proc[i] = 1;
for (auto [j, w] : adj[i]) {
if (j == p) {
continue;
}
dfs(j, i, d+w);
}
}
void dfsdist(long long int i, long long int p, long long int id) {
for (auto [j, w] : adj[i]) {
if (j == p) {
continue;
}
dist[j][id] = dist[i][id]+w;
dfsdist(j, i, id);
}
}
void ch(long long int i, long long int p) {
if (max(dist[i][0], dist[i][1]) < nod) {
no = i, nod = max(dist[i][0], dist[i][1]);
}
for (auto [j, _] : adj[i]) {
if (j == p) {
continue;
}
ch(j, i);
}
}
pair<long long int, long long int> calc(long long int i) {
long long int a, b;
no = i, nod = 0;
dfs(i, -1, 0);
a = no, no = i, nod = 0;
dfs(a, -1, 0);
b = no;
dfsdist(a, -1, 0);
dfsdist(b, -1, 1);
no = i, nod = INT64_MAX;
ch(i, -1);
return {nod, no};
}
int travelTime(int n, int m, int l, int A[], int B[], int T[]) {
vector<pair<long long int, long long int>> comp;
for (long long int i = 0; i < m; i++) {
adj[A[i]].push_back({B[i], T[i]});
adj[B[i]].push_back({A[i], T[i]});
}
for (long long int i = 0; i < n; i++) {
if (proc[i]) {
continue;
}
comp.push_back(calc(i));
}
sort(comp.rbegin(), comp.rend());
deque<pair<long long int, long long int>> a;
bool f = 0;
for (long long int i = 0; i < comp.size(); i += 2) {
if (f) {
a.push_front(comp[i]);
if (i+1 < comp.size()) {
a.push_back(comp[i+1]);
}
} else {
a.push_back(comp[i]);
if (i+1 < comp.size()) {
a.push_front(comp[i+1]);
}
}
f ^= 1;
}
for (long long int i = 1; i < a.size(); i++) {
adj[a[i-1].second].push_back({a[i].second, l});
adj[a[i].second].push_back({a[i-1].second, l});
}
long long int a1, b1;
no = 0, nod = 0;
for (long long int i = 0; i < n; i++) {
dist[i][0] = 0;
}
dfs(0, -1, 0);
a1 = no, no = 0, nod = 0;
dfs(a1, -1, 0);
b1 = no;
dfsdist(a1, -1, 0);
return dist[b1][0];
}
