#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;
int res = 2e9;
dist[d.first] = 0;
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;
vector < int > x;
for(int i = 0; i < n; i++) {
if(!used[i]) {
res = max(res, getDiam(i).first);
x.push_back(getHalfDiam(i));
}
}
sort(x.begin(), x.end());
if(x.size() >= 3) {
res = max(res, x[x.size() - 2] + x[x.size() - 3] + 2 * l);
}
if(x.size() >= 2) {
res = max(res, x[x.size() - 1] + x[x.size() - 2] + l);
}
return res;
}
