#include "dreaming.h"
#include <bits/stdc++.h>
#define pb emplace_back
#define fi first
#define se second
#define mp make_pair
#define ll long long
using namespace std;
vector<pair<ll, ll>> conn[100005];
bool vi[100005];
bool vi2[100005];
ll par2[100005];
ll dk2[100005];
vector<ll> dia, hf;
ll md, mdx;
void dfs(ll now, ll 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(ll now, ll 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(ll 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';
ll an = md;
ll 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(ll 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 if(dia.size() == 2) return max(dia[0], hf[0] + hf[1] + l);
else return max(dia[0], max(hf[0] + hf[1] + l, hf[1] + hf[2] + l * 2));
}
