#include "dreaming.h"
#include <bits/stdc++.h>
using namespace std;
int n, m, l;
const int N =100005;
bool vis[N];
multiset<int> ms[N];
vector<array<int, 2>> adj[N];
vector<array<int, 2>> comp;
int dfs1(int node, int par)
{
vis[node] = true;
int res = 0;
ms[node].insert(0);
for (auto next : adj[node])
{
if (next[0] == par) continue;
int cur = dfs1(next[0], node) + next[1];
res = max(res, cur);
ms[node].insert(cur);
}
return res;
}
int dfs2(int node, int par, int pdist)
{
if (par != -1)
{
int del = *ms[node].rbegin() + pdist;
ms[par].erase(ms[par].find(del));
ms[node].insert(*ms[par].rbegin() + pdist);
ms[par].insert(del);
}
int res = *ms[node].rbegin();
for (auto next : adj[node])
{
if (next[0] == par) continue;
res = min(res, dfs2(next[0], node, next[1]));
}
return res;
}
array<int, 2> dfs3(int node, int par)
{
array<int, 2> best = {node, 0};
for (auto next : adj[node])
{
if (next[0] == par) continue;
auto cur = dfs3(next[0],node);
cur[1] += next[1];
if (cur[1] > best[1])
{
best = cur;
}
}
return best;
}
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++)
{
adj[A[i]].push_back({B[i], T[i]});
adj[B[i]].push_back({A[i], T[i]});
}
for (int i = 0; i < n; i++)
{
if (!vis[i])
{
dfs1(i, -1);
int cent = dfs2(i, -1, -1);
auto cur = dfs3(i, -1);
int mdist = dfs3(cur[0], -1)[1];
comp.push_back({cent, mdist});
}
}
return max({comp[0][0] + comp[1][0] + l, comp[0][1], comp[1][1]});
}
