#include <iostream>
#include <cstdio>
#include <vector>
#include <array>
#include <string>
#include <algorithm>
#include <numeric>
#include <map>
#include <unordered_map>
#include <set>
#include <unordered_set>
#include <queue>
#include <cmath>
#include <climits>
#include <iomanip>
#include <limits>
#include <tuple>
#include <stack>
#include <bitset>
#include <cstring>
#include <sstream>
#include <functional>
#include <random>
#include "dreaming.h"
using namespace std;
using ll = long long;
const ll inf = (1ll << 60);
vector<vector<pair<int, int>>> adj;
vector<int> par;
vector<bool> vis;
vector<int> comp;
vector<bool> incomp;
vector<ll> distg;
int compB = -1, compC = -1;
void mark_cmp(int u) {
vis[u] = true;
comp.push_back(u);
for (auto& e : adj[u]) {
int v = e.first;
if (!vis[v]) {
mark_cmp(v);
}
}
}
void dfs(int u, int p, ll d, pair<int, ll>& mx) {
distg[u] = d;
if (d > mx.second) {
mx = { u, d };
}
par[u] = p;
for (auto& e : adj[u]) {
int v = e.first, w = e.second;
if (v == p) {
continue;
}
dfs(v, u, d + w, mx);
}
}
pair<int, ll> find_centar(int s) {
for (auto& v : comp) {
par[v] = -1;
distg[v] = 0;
}
pair<int, ll> mx = { -1, -1 };
dfs(s, -1, 0, mx);
int B = mx.first;
for (auto& v : comp) {
par[v] = -1;
distg[v] = 0;
}
mx = { -1, -1 };
dfs(B, -1, 0, mx);
int C = mx.first;
ll tot = mx.second;
compB = B, compC = C;
vector<int> path;
for (int v = C; v != -1; v = par[v]) {
path.push_back(v);
}
reverse(path.begin(), path.end());
vector<int> dist(path.size(), 0);
for (int i = 1; i < path.size(); ++i) {
int a = path[i - 1], b = path[i];
for (auto& e : adj[a]) {
if (e.first == b) {
dist[i] = dist[i - 1] + e.second;
break;
}
}
}
for (int i = 0; i < path.size(); ++i) {
if (dist[i] * 2 >= tot) {
return { path[i], tot };
}
}
return { path.back(), tot };
}
int mx_dist(int s) {
for (auto& v : comp) {
par[v] = -1;
distg[v] = 0;
}
pair<int, ll> mx = { -1, -1 };
dfs(s, -1, 0, mx);
return mx.second;
}
int travelTime(int N, int M, int L, int A[], int B[], int T[]) {
int n, m, l;
n = N, m = M, l = L;
adj.assign(n, {});
for (int i = 0; i < m; ++i) {
int u, v, w;
u = A[i], v = B[i], w = T[i];
adj[u].push_back({ v, w });
adj[v].push_back({ u, w });
}
vis.assign(n, false);
par.assign(n, -1);
distg.assign(n, 0);
vector<ll> distB(n, inf), distC(n, inf);
vector<ll> c;
c.reserve(n);
ll pom = 0;
for (int u = 0; u < n; ++u) {
if (!vis[u]) {
comp.clear();
mark_cmp(u);
for (auto& v : comp) {
par[v] = -1;
distg[v] = 0;
}
pair<int, ll> x = find_centar(u);
for (auto& v : comp) {
distB[v] = inf;
}
for (auto& v : comp) {
par[v] = -1;
distg[v] = 0;
}
pair<int, ll> mx = { -1, -1 };
dfs(compB, -1, 0, mx);
for (auto& v : comp) {
distB[v] = distg[v];
}
for (auto& v : comp) {
distC[v] = inf;
}
for (auto& v : comp) {
par[v] = -1;
distg[v] = 0;
}
mx = { -1, -1 };
dfs(compC, -1, 0, mx);
for (auto& v : comp) {
distC[v] = distg[v];
}
ll r = inf;
for (auto& v : comp) {
ll ecc = max(distB[v], distC[v]);
if (ecc < r) {
r = ecc;
}
}
c.push_back(r);
pom = max(pom, x.second);
}
}
ll ans = pom;
sort(c.rbegin(), c.rend());
if (c.size() == 1) {
//ans = pom;
}
else if (c.size() == 2) {
ans = max(ans, c[0] + l + c[1]);
}
else {
ans = max({ ans, c[1] + l + c[0], c[1] + 2ll * l + c[2] });
}
return ans;
}
