#include "dreaming.h"
#include <bits/stdc++.h>
using namespace std;
typedef pair<int, int> pi;
int d[100000], fr[100000], v[100000];
vector<int> radii;
vector<pi> adj[100000];
pi dfs1(long long node, long long parent, long long distance){
v[node] = 1;
pi p = pi(node, distance);
for(auto it : adj[node]){
if(!d[it.first] && it.first != parent){
pi q = dfs1(it.first, node, distance+it.second);
if(q.second > p.second) p = q;
}
}
return p;
}
pi dfs2(long long node, long long parent, long long distance){
v[node] = 1;
d[node] = distance;
fr[node] = parent;
pi p = pi(node, distance);
for(auto it : adj[node]){
if(!d[it.first] && it.first != parent){
pi q = dfs2(it.first, node, distance+it.second);
if(q.second > p.second) p = q;
}
}
return p;
}
int travelTime(int N, int M, int L, int A[], int B[], int T[]) {
int c, maxd = 0, r, ans = 0;
pi f, l;
for(int i = 0; i < M; i++){
adj[A[i]].push_back(pi(B[i], T[i]));
adj[B[i]].push_back(pi(A[i], T[i]));
}
memset(fr, -1, sizeof(fr));
for(int i = 0; i < N; i++){
if(v[i]) continue;
f = dfs1(i, i, 0);
l = dfs2(f.first, f.first, 0);
maxd = max(maxd, l.second);
c = l.first;
r = l.second;
while(true){
r = min(r, max(d[c], l.second-d[c]));
if(c == fr[c]) break;
c = fr[c];
}
radii.push_back(r);
}
sort(radii.begin(), radii.end());
reverse(radii.begin(), radii.end());
ans = maxd;
if(radii.size() > 1) ans = max(ans, radii[0]+radii[1]+L);
if(radii.size() > 2) ans = max(ans, radii[1]+radii[2]+2*L);
return ans;
}
