#include "dreaming.h"
#include <bits/stdc++.h>
using namespace std;
//#define ONLINE_JUDGE
#ifdef ONLINE_JUDGE
#define debug(x) cout << (#x) << ": " << (x) << "\n"
#else
#define debug(x)
#endif
#define pb push_back
constexpr static int MXSIZE = 100000;
vector<array<int, 2>> g[MXSIZE];
int max_dist[MXSIZE];
int component[MXSIZE];
int radius[MXSIZE];
int n, m, l;
int worst;
void dfs1(int node, int parent, int comp)
{
component[node] = comp;
for (auto [c, cc] : g[node])
{
if (c != parent)
{
dfs1(c, node, comp);
max_dist[node] = max(max_dist[node], max_dist[c] + cc);
}
}
}
void dfs2(int node, int parent, int cdist)
{
vector<int> dd(3);
for (auto [c, cc] : g[node])
{
if (c == parent)
continue;
dd[0] = max_dist[c] + cc;
sort(dd.begin(), dd.end());
}
worst = max(worst, dd[1] + dd[2]);
radius[component[node]] = min(radius[component[node]], max(dd[2], cdist));
for (auto [c, cc] : g[node])
{
if (c == parent)
continue;
int j = 2;
if (max_dist[c]+cc == dd[j])
j--;
dfs2(c, node, max(cdist, dd[j]) + cc);
}
}
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++)
{
g[A[i]].pb({B[i], T[i]});
g[B[i]].pb({A[i], T[i]});
}
for (int i = 0; i < n; i++)
component[i] = -1;
int k = 0;
for (int i = 0; i < n; i++)
{
if (component[i] == -1)
{
radius[k] = 1e9;
dfs1(i, -1, k++);
dfs2(i, -1, 0);
if (radius[k-1] == 10)
debug(i);
}
}
sort(radius, radius + k);
debug(worst);
debug(k);
debug(radius[k-1]);
debug(radius[k-2]);
debug(radius[k-3]);
if (k >= 2)
worst = max(worst, radius[k-1] + radius[k-2] + l);
if (k >= 3)
worst = max(worst, radius[k-2] + radius[k-3] + 2 * l);
return worst;
}
