#include "dreaming.h"
#include <bits/stdc++.h>
#define pb emplace_back
#define fi first
#define se second
#define mp make_pair
using namespace std;
vector<pair<int, int>> conn[100005];
bool vi[100005];
bool vi2[100005];
int par2[100005];
int dk2[100005];
vector<int> dia, hf;
int md, mdx;
void dfs(int now, int di) {
if(vi[now]) return;
vi[now] = true;
if(di > md) {
md = di;
mdx = now;
}
for(auto x: conn[now]) dfs(x.fi, di + x.se);
}
void dfs2(int now, int di) {
if(vi2[now]) return;
vi2[now] = true;
if(di > md) {
md = di;
mdx = now;
}
for(auto x: conn[now]) {
if(!vi2[x.fi]){
par2[x.fi] = now;
dk2[x.fi] = x.se;
dfs2(x.fi, di + x.se);
}
}
}
void once(int a) {
md = 0, mdx = a;
dfs(a, 0);
cerr << a << ' ' << md << '\n';
md = 0;
par2[mdx] = -1;
dfs2(mdx, 0);
dia.pb(md);
cerr << a << ' ' << md << '\n';
int an = md;
int tt = md;
while(mdx != -1) {
an = min(an, max(md, tt - md));
md -= dk2[mdx];
mdx = par2[mdx];
}
cerr << a << ' ' << an << '\n';
hf.pb(an);
}
int travelTime(int n, int m, int l, int a[], int b[], int t[]) {
for(int i = 0; i < m; i++) {
conn[a[i]].pb(mp(b[i], t[i]));
conn[b[i]].pb(mp(a[i], t[i]));
}
for(int i = 0; i < n; i++) {
if(vi[i]) continue;
else once(i);
}
sort(dia.begin(), dia.end()); reverse(dia.begin(), dia.end());
sort(hf.begin(), hf.end()); reverse(hf.begin(), hf.end());
if(dia.size() == 1) return dia[0];
else return max(dia[0], hf[0] + hf[1] + l);
}
