#include "dreaming.h"
#include <bits/stdc++.h>
#define X first
#define Y second
using namespace std;
vector<pair<int, int> > adj[100005];
vector<int> dists;
bool visited[100005];
int dpd[100005];
int maxd[100005][2];
int ans, i;
int dfs1(int x) {
int ans = 0;
visited[x] = true;
int max1 = 0;
int max2 = 0;
dpd[x] = 0;
for (auto y : adj[x]) {
if (!visited[y.X]) {
ans = max(ans, dfs1(y.X));
dpd[x] = max(dpd[x], dpd[y.X]+y.Y);
if (dpd[y.X]+y.Y >= max1) {
max2 = max1;
max1 = dpd[y.X]+y.Y;
}
else if (dpd[y.X]+y.Y >= max2) {
max2 = dpd[y.X]+y.Y;
}
}
}
maxd[x][0] = max1;
maxd[x][1] = max2;
return max(ans, max1+max2);
}
void swaping(int x, int y, int z, bool ok) {
if (maxd[x][0] == dpd[y]+z) {
dpd[x]=maxd[x][1];
}
else {
dpd[x] = maxd[x][0];
}
if (ok) {
if (dpd[x]+z >= maxd[y][0]) {
maxd[y][1] = maxd[y][0];
maxd[y][0] = dpd[x]+z;
}
else if (dpd[x]+z>maxd[y][1]) {
maxd[y][1] = dpd[x]+z;
}
}
dpd[y] = maxd[y][0];
return;
}
int dfs2(int x, int p=-1) {
int ans = dpd[x];
for (auto y : adj[x]) {
if (y.X != p) {
swaping(x, y.X, y.Y, true);
ans = min(ans, dfs2(y.X, x));
swaping(y.X, x, y.Y, false);
}
}
return ans;
}
int travelTime(int n, int m, int l, int A[], int B[], int T[]) {
fill(visited, visited+n+2, false);
fill(dpd, dpd+n+2, 0);
for (i=0; i < m; ++i) {
adj[A[i]].push_back(make_pair(B[i], T[i]));
adj[B[i]].push_back(make_pair(A[i], T[i]));
}
ans = 0;
for (i=0; i < n; ++i) {
if (!visited[i]) {
ans = max(ans, dfs1(i));
dists.push_back(dfs2(i));
}
}
sort(dists.begin(), dists.end(), greater<int>());
if (dists.size() == 1) {
return max(ans, dists[0]);
}
else if (dists.size() == 2) {
return max(ans, dists[0]+dists[1]+l);
}
else {
return max({ans, dists[0]+dists[1]+l, dists[1]+dists[2]+2*l});
}
}
