#include "dreaming.h"
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
ll rd[100000];
bool vis[100000];
struct W {
int t;
int w;
};
vector<vector<W>> al;
void calcrd(int v, int p) {
vis[v] = true;
ll mrd = 0;
for(auto a : al[v]) {
if(a.t == p) continue;
calcrd(a.t, v);
mrd = max(mrd, a.w + rd[a.t]);
}
rd[v] = mrd;
}
ll md = 0;
ll radius(int v, int p, ll tdist) {
int mrv = -1;
ll mr = tdist;
ll mr2 = tdist;
for(auto a : al[v]) {
if(a.t == p) continue;
if(rd[a.t] + a.w >= mr) {
mrv = a.t;
mr2 = mr;
mr = rd[a.t] + a.w;
} else if(rd[a.t] + a.w >= mr2) {
mr2 = rd[a.t] + a.w;
}
}
if(mrv == -1) md = max(md, mr);
else md = max(md, mr + mr2);
ll br = mr;
for(auto a : al[v]) {
if(a.t == p) continue;
if(a.t == mrv) {
br = min(br, radius(a.t, v, mr2 + a.w));
} else {
br = min(br, radius(a.t, v, mr + a.w));
}
}
return br;
}
int travelTime(int N, int M, int L, int A[], int B[], int T[]) {
al.assign(N, {});
for(int i = 0; i < M; ++i) {
al[A[i]].push_back({B[i], T[i]});
al[B[i]].push_back({A[i], T[i]});
}
vector<ll> rads;
for(int i = 0; i < N; ++i) {
if(vis[i]) continue;
calcrd(i, -1);
rads.push_back(radius(i, -1, 0));
}
sort(begin(rads), end(rads), greater<ll>{});
ll mr;
if(rads.size() == 1) mr = rads[0];
else if(rads.size() == 2) mr = rads[0] + L + rads[1];
else mr = max(rads[0] + rads[1] + L, rads[1] + 2*L + rads[2]);
return max(md, mr);
}
