#include "dreaming.h"
#include <bits/stdc++.h>
using namespace std;
int dist[100000], prv[100000], idx;
vector<pair<int, int>> adj[100000];
vector<int> v, path, tmp;
void dfs(int x, int p) {
if(dist[x] > dist[idx]) idx = x;
tmp.push_back(x);
prv[x] = p;
for(auto i : adj[x]) if(i.first != p) {
if(dist[i.first] == -1) {
dist[i.first] = dist[x]+i.second;
dfs(i.first, x);
}
}
}
int travelTime(int N, int M, int L, int A[], int B[], int T[]) {
for(int i = 0; i < M; i++) {
adj[A[i]].push_back({B[i], T[i]});
adj[B[i]].push_back({A[i], T[i]});
}
memset(dist, -1, sizeof(dist));
for(int i = 0; i < N; i++) {
if(dist[i] != -1) continue;
idx = i;
dist[i] = 0;
dfs(i, -1);
while(tmp.size()) {
dist[tmp.back()] = -1;
tmp.pop_back();
}
dist[idx] = 0;
dfs(idx, -1);
tmp.clear();
int cur = (int)1e9;
for(int j = idx; j != -1; j = prv[j]) path.push_back(j);
for(int j : path) cur = min(cur, max(dist[j], dist[idx]-dist[j]));
v.push_back(cur);
path.clear();
}
sort(v.begin(), v.end(), greater<int>());
if(v.size() == 1) return v[0];
if(v.size() == 2) return v[0]+v[1]+L;
return max(v[0]+v[1]+L, v[1]+v[2]+2*L);
}
