#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+1);
vector<bool> visited(1e5+1);
vi parent(1e5+1), dists(1e5+1);
ll maxe = 0, maxnode = -1;
void dfs(ll x, ll p=-1, ll dist=0){
visited[x] = 1;
parent[x] = p;
dists[x] = dist;
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]});
}
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;
vector<pair<ll, ll>> path;
while(n2 != n1){
path.pb({n2, dists[n2]});
n2 = parent[n2];
}
path.pb({n2, dists[n2]});
reverse(path.begin(), path.end());
ll diameter = path.back().second;
ll best_node = -1, best_dist = 1e18;
for(int j = 0; j < path.size(); j++){
if(max(path[j].s, diameter - path[j].s) < best_dist){
best_node = path[j].f;
best_dist = max(path[j].s, diameter - path[j].s);
}
}
centers.pb({best_dist, best_node});
}
}
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});
}
dfs(0);
maxe = 0;
dfs(maxnode);
return dists[maxnode];
}
