#include <bits/stdc++.h>
#define IOS ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define endl "\n"
#include "dreaming.h"
using ll = long long;
using namespace std;
class DSU {
public:
vector<int> parent, sz;
DSU(ll x) {
parent.resize(x);
sz.resize(x, 1);
iota(parent.begin(), parent.end(), 0);
}
ll find_parent(ll x) {
if (parent[x] != x)
parent[x] = find_parent(parent[x]);
return parent[x];
}
void unite(ll x, ll y) {
ll parx = find_parent(x);
ll pary = find_parent(y);
if (parx == pary) return;
if (sz[pary] > sz[parx]) swap(parx, pary);
parent[pary] = parx;
sz[parx] += sz[pary];
}
bool same(ll x, ll y) {
return find_parent(x) == find_parent(y);
}
};
vector<ll> dijkstra(ll src, vector<vector<pair<int, int>>> &adj) {
vector<ll> dist(adj.size(), LLONG_MAX);
priority_queue<pair<ll, ll>, vector<pair<ll, ll>>, greater<>> pq;
dist[src] = 0;
pq.push({0, src});
while (!pq.empty()) {
auto [weight, cur] = pq.top(); pq.pop();
if (weight > dist[cur]) continue;
for (auto [to, to_w] : adj[cur]) {
if (dist[to] > to_w + dist[cur]) {
dist[to] = to_w + dist[cur];
pq.push({dist[to], to});
}
}
}
return dist;
}
int travelTime(int N, int M, int L, int A[], int B[], int T[]) {
if (M == 0) {
cout << 2 * L << endl;
return 0;
}
vector<vector<pair<int, int>>> adj(N);
DSU dsu(N);
for (int i = 0; i < M; ++i) {
adj[A[i]].emplace_back(B[i], T[i]);
adj[B[i]].emplace_back(A[i], T[i]);
dsu.unite(A[i], B[i]);
}
map<int, vector<int>> components;
for (int i = 0; i < N; ++i) {
components[dsu.find_parent(i)].push_back(i);
}
vector<ll> sort_ecc;
map<int, ll> ecc_by_root;
for (auto &[root, nodes] : components) {
ll min_ecc = LLONG_MAX;
for (int u : nodes) {
vector<ll> dist = dijkstra(u, adj);
ll ecc = 0;
for (int v : nodes) {
if (dist[v] != LLONG_MAX) {
ecc = max(ecc, dist[v]);
}
}
min_ecc = min(min_ecc, ecc);
}
ecc_by_root[root] = min_ecc;
sort_ecc.push_back(min_ecc);
}
sort(sort_ecc.rbegin(), sort_ecc.rend());
ll cur_ecc = sort_ecc[0];
int dia_root = -1;
for (auto &[root, ecc] : ecc_by_root) {
if (ecc == cur_ecc) {
dia_root = root;
break;
}
}
vector<int> &main_nodes = components[dia_root];
int start = main_nodes[0];
vector<ll> d1 = dijkstra(start, adj);
int far1 = start;
for (int v : main_nodes) {
if (d1[v] != LLONG_MAX && d1[v] > d1[far1])
far1 = v;
}
vector<ll> d2 = dijkstra(far1, adj);
int far2 = far1;
for (int v : main_nodes) {
if (d2[v] != LLONG_MAX && d2[v] > d2[far2])
far2 = v;
}
ll cur_dia = d2[far2];
for (int i = 1; i < sort_ecc.size(); ++i) {
cur_dia = max(cur_dia, cur_ecc + sort_ecc[i] + L);
}
cout << cur_dia << endl;
}
