#include "dreaming.h"
#include <bits/stdc++.h>
using namespace std;
vector<vector<pair<int,int>>>adj;
bool vis[100000];
map<int,int>mp,cnt;
vector<int>connect;
int dd(int node, int e) {
vis[node]=true;
int mx = 0, prev = node;
for(auto z : adj[node]) {
if(z.first == e) continue;
auto ret = dd(z.first,node);
if(mx <= ret+z.second)
mx=ret+z.second,prev=z.first;
}
mp[node]=prev,cnt[node]=mx;
return mx;
}
pair<int,int> d(int node, int e) {
vis[node]=true;
pair<int,int>mx = {0,node};
for(auto z : adj[node]) {
if(z.first == e) continue;
auto ret = d(z.first,node);
if(mx.first <= ret.first+z.second)
mx.first=ret.first+z.second,mx.second=ret.second;
}
return mx;
}
void dia(int node) {
int nd = d(node,-1).second;
auto ans = dd(nd,-1);
int curr = nd;
while(cnt[mp[curr]] > ans/2) curr=mp[curr];
if(cnt[curr] <= ans - cnt[mp[curr]]) {
connect.push_back(curr);
} else connect.push_back(mp[curr]);
return;
}
int travelTime(int n, int m, int l, int a[], int b[], int t[]) {
adj.resize(n);
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(vis[i]) continue;
dia(i);
}
for(int i = 0 ; i < (int)connect.size()-1 ; i++) {
adj[connect[i]].push_back(make_pair(connect[i+1],l));
adj[connect[i+1]].push_back(make_pair(connect[i],l));
}
int edge = d(0,-1).second;
return d(edge,-1).first;
}
