#include <bits/stdc++.h>
#include "dreaming.h"
using namespace std;
#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
typedef long long ll;
typedef vector<int> vi;
typedef pair<int, int> pi;
#define pb push_back
#define mp make_pair
#define f first
#define s second
vector<vector<pi>> adj(1e5+5);
vector<bool> visited(1e5+5);
vi parent(1e5+5);
ll maxe = -1, maxnode = -1;
map<pi, int> cost;
void dfs(ll x, ll p=-1, ll dist=0){
visited[x] = 1;
parent[x] = p;
if(dist > maxe){
maxe = dist;
maxnode = x;
}
for(auto i : adj[x]){
if(i.f != p)
dfs(i.f, x, dist + i.s);
}
}
int travelTime(int N, int M, int L, int A[], int B[], int T[]){
for(int i = 0; i < M; i++){
adj[A[i]].pb({B[i], T[i]});
adj[B[i]].pb({A[i], T[i]});
cost[{A[i], B[i]}] = cost[{B[i], A[i]}] = T[i];
}
vector<pair<ll, ll>> centers;
for(int i = 0; i < N; i++){
if(!visited[i]){
maxe = 0, maxnode = -1;
dfs(i);
if(maxnode == -1){
centers.pb({0, i});
continue;
}
ll n1 = maxnode;
maxe = 0, maxnode = -1;
dfs(n1);
ll n2 = maxnode;
vi path;
while(n2 != n1){
path.pb(n2);
n2 = parent[n2];
}
path.pb(n2);
ll cur = 0, best_res = 1e18, best_v = path[0];
for (int j = 1; j < path.size(); j++) {
cur += cost[{path[j], path[j - 1]}];
//cout << cur << '\n';
if (max(cur, maxe - cur) < best_res) {
best_res = max(cur, maxe - cur);
best_v = path[j];
}
}
centers.push_back({best_res, best_v});
}
}
/*for(auto i : centers)
cout << i.f << ' ' << i.s << '\n';
cout << '\n';*/
sort(centers.begin(), centers.end(), greater<pair<ll, ll>>());
for(int i = 1; i < centers.size(); i++){
adj[centers[0].s].pb({centers[i].s, L});
adj[centers[i].s].pb({centers[0].s, L});
}
/*for(int i = 0; i < N; i++){
cout << i << ":\n";
for(auto j : adj[i]){
cout << j.f << ' ' << j.s << '\n';
}
cout << '\n';
}*/
dfs(0);
maxe = 0;
dfs(maxnode);
return maxe;
}
