#include "dreaming.h"
#include <bits/stdc++.h>
using namespace std;
using pii = pair < int, int >;
const int DIM = 100007;
int n, m, l;
vector < pii > v[DIM];
bool used[DIM];
int dist[DIM];
void countDist(int val, int prev, int& v1) {
if(dist[val] > dist[v1]) v1 = val;
for(auto e: v[val]) {
if(e.first == prev) continue;
dist[e.first] = dist[val] + e.second;
countDist(e.first, val, v1);
}
}
pair < int, pii > getDiam(int root) {
int v1 = root, v2 = root;
dist[root] = 0;
countDist(root, root, v1);
dist[v1] = 0;
countDist(v1, v1, v2);
return {dist[v2], {v1, v2}};
}
bool dfs(int val, int prev, int v2, int& res) {
used[val] = true;
bool flag = (val == v2);
for(auto e: v[val]) {
if(e.first == prev) continue;
if(dfs(e.first, val, v2, res)) flag = true;
}
if(flag) {
res = min(res, max(dist[val], dist[v2] - dist[val]));
return true;
}
return false;
}
int getHalfDiam(int root) {
pii d = getDiam(root).second;
int tmp = root;
dist[d.first] = 0;
int res = 2e9;
countDist(d.first, d.first, tmp);
dfs(d.first, d.first, d.second, res);
return res;
}
int travelTime(int N, int M, int L, int A[], int B[], int T[]) {
n = N; m = M, l = L;
for(int i = 0; i < m; i++) {
v[A[i]].push_back({ B[i], T[i] });
v[B[i]].push_back({ A[i], T[i] });
}
if(m == n - 1) return getDiam(0).first;
int res = -2e9;
int mx1 = -2e9, mx2 = -2e9;
for(int i = 0; i < n; i++) {
if(!used[i]) {
res = max(res, getDiam(i).first);
int tmp = getHalfDiam(i);
if(tmp >= mx1) {
mx2 = mx1;
mx1 = tmp;
}
else if(tmp >= mx2) {
mx2 = tmp;
}
}
}
res = max(res, l + mx1 + mx2);
return res;
}
