#include "dreaming.h"
#include <bits/stdc++.h>
#define ll long long
#define inf INT_MAX
using namespace std;
const int mxn = 100005;
vector<pair<int, int>> g[mxn];
vector<int> group;
int mx = 0;
bool visited[mxn];
void dfs(int n, int p, int d, vector<pair<int, int>> &path) {
visited[n] = true;
path.push_back({n, d});
for (auto x : g[n]) {
if (p != x.first) {
dfs(x.first, n, d + x.second, path);
}
}
}
int findDist(int n) {
vector<pair<int, int>> d;
dfs(n, -1, 0, d);
int node, maxDist = -1;
for (auto x : d) {
if (x.second > maxDist) {
maxDist = x.second;
node = x.first;
}
}
d.clear();
dfs(node, -1, 0, d);
map<int, int> mp;
maxDist = -1;
for (auto x : d) {
mp[x.first] = x.second;
if (x.second > maxDist) {
maxDist = x.second;
node = x.first;
}
}
mx = max(mx, maxDist);
d.clear();
dfs(node, -1, 0, d);
int ans = inf;
for (auto x : d) {
ans = min(ans, max(x.second, mp[x.first]));
}
return ans;
}
int travelTime(int n, int m, int L, int A[], int B[], int T[]) {
for (int i = 0; i < m; i++) {
g[A[i]].push_back({B[i], T[i]});
g[B[i]].push_back({A[i], T[i]});
}
vector<int> groups;
for (int i = 0; i < n; i++) {
if (visited[i]) continue;
groups.push_back(findDist(i));
}
sort(groups.rbegin(),groups.rend());
if (groups.size() == 1) return max(groups[0], mx);
if (groups.size() == 2) return max(groups[0] + groups[1] + L, mx);
return max({groups[0] + groups[1] + L, groups[1] + groups[2] + 2 * L, mx});
}
