#include<bits/stdc++.h>
#include "dreaming.h"
using namespace std;
const int big = 1e5+5;
int cnt = 0, color[big] = {0}, vex[big] = {0};
bool colvis[big] = {false};
vector<vector<pair<int,int>>> adj(big);
int bag, bigdeez;
int centers[big] = {0}, par[big], wt[big];
void coldfs(int x){
if(colvis[x]) return;
if(color[x] == 0){cnt++; color[x] = cnt; vex[cnt] = x;}
colvis[x] = true;
for(auto &y : adj[x]){
if(colvis[y.first]) continue;
color[y.first] = color[x];
coldfs(y.first);
}
}
int v; long long mx;
void dfs(int x, int p, int d){
if(d > mx){mx = d; v = x;}
for(auto &y : adj[x]){
if(y.first == p) continue;
dfs(y.first, x, d + y.second);
}
}
void dfs2(int x, int p, int d){
par[x] = p;
wt[x] = 0;
if(d > mx){mx = d; v = x;}
for(auto &y : adj[x]){
if(y.first == p) continue;
wt[y.first] = y.second;
dfs2(y.first, x, d + y.second);
}
}
int travelTime(int n, int m, int l, int a[], int b[], int t[]){
long long btt = 0; int cc;
for(int i = 0; i < m; i++){
adj[a[i]].push_back(make_pair(b[i],t[i]));
adj[b[i]].push_back(make_pair(a[i],t[i]));
}
for (int i = 0; i < n; i++) {
if (!colvis[i]) coldfs(i);
}
for(int i=1; i <= cnt; i++){
int s = vex[i];
mx = 0; dfs(s, -1, 0);
mx = 0; dfs2(v, -1, 0);
int k = v, ct = v;
long long best = 0, curr = mx;
while(k != -1){
curr -= wt[k]; long long wgt = min(curr, mx - curr);
best = max(best, wgt);
if(best == wgt){ct = k;}
k = par[k];
}
centers[i] = ct;
if(best >= btt){btt = best; cc = ct;}
}
for(int i = 1; i < cnt; i++){
if(centers[i] == cc) continue;
adj[centers[i]].push_back(make_pair(cc, l));
adj[cc].push_back({centers[i], l});
}
mx = 0; dfs(0,-1,0);
mx = 0; dfs(v,-1,0);
return mx;
}
