#include "dreaming.h"
#include <bits/stdc++.h>
using namespace std;
#define ll long long
const int nx = 1e5 + 5;
int n, m; ll l;
int pa[nx];
ll d[nx], r[nx];
ll dist1[nx], dist2[nx];
vector<int> dsu[nx];
vector<pair<int,ll>> adj[nx];
bool vis[nx];
int fp(int n) {
if (pa[n] == n) return n;
return pa[n] = fp(pa[n]);
}
void unite(int u, int v) {
int pu = fp(u), pv = fp(v);
if (pu == pv) return;
pa[pu] = pv;
}
void process(int u) {
for (auto idx : dsu[u]) dist1[idx] = 1e18, dist2[idx] = 1e18;
u = fp(u);
vis[u] = 1;
priority_queue<pair<ll,int>,vector<pair<ll,int>>,greater<pair<ll,int>>> pq;
pq.emplace(0, dsu[u][0]);
dist1[dsu[u][0]] = 0;
int root1, root2;
ll mx = 0;
while (!pq.empty()) {
auto [w, u] = pq.top();
pq.pop();
if (dist1[u] < w) continue;
for (auto [v, ww] : adj[u]) {
if (dist1[v] <= w + ww) continue;
dist1[v] = w + ww;
pq.emplace(dist1[v], v);
}
}
for (auto idx : dsu[u]) {
if (dist1[idx] >= mx) {
mx = dist1[idx], root1 = idx;
}
}
mx = 0;
dist2[root1] = 0;
pq.emplace(0, root1);
while (!pq.empty()) {
auto [w, u] = pq.top();
pq.pop();
if (dist2[u] < w) continue;
for (auto [v, ww] : adj[u]) {
if (dist2[v] <= w + ww) continue;
dist2[v] = w + ww;
pq.emplace(dist2[v], v);
}
}
for (auto idx : dsu[u]) {
if (dist2[idx] >= mx) {
mx = dist2[idx], root2 = idx;
}
dist1[idx] = 1e18;
}
d[u] = mx;
mx = 0;
dist1[root2] = 0;
pq.emplace(0, root2);
while (!pq.empty()) {
auto [w, u] = pq.top();
pq.pop();
if (dist1[u] < w) continue;
for (auto [v, ww] : adj[u]) {
if (dist1[v] <= w + ww) continue;
dist1[v] = w + ww;
pq.emplace(dist1[v], v);
}
}
for (auto idx : dsu[u]) {
if (dist1[idx] >= mx) {
mx = dist1[idx], root1 = idx;
}
}
r[u] = 1e18;
for (auto idx : dsu[u]) {
r[u] = min(r[u], max(dist1[idx], dist2[idx]));
}
}
int travelTime(int N, int M, int L, int A[], int B[], int T[]) {
n = N, m = M, l = L;
for (int i = 1; i <= n - 1; i++) pa[i] = i;
for (int i = 1; i <= m; i++) {
int a, b; ll t;
a = A[i - 1], b = B[i - 1], t = T[i - 1];
adj[a].emplace_back(b, t);
adj[b].emplace_back(a, t);
unite(a, b);
}
for (int i = 0; i < n; i++) dsu[fp(i)].emplace_back(i);
for (int i = 0; i < n; i++) {
if (vis[fp(i)]) continue;
if (dsu[fp(i)].empty()) continue;
process(i);
}
ll D = 0;
for (int i = 0; i < n; i++) {
D = max(D, d[fp(i)]);
}
int center;
ll mx = 0;
for (int i = 0; i < n; i++) {
if (r[fp(i)] >= mx) {
mx = r[fp(i)];
center = fp(i);
}
}
vector<pair<ll,int>> v;
for (int i = 0; i < n; i++) {
if (fp(i) != center) v.emplace_back(r[fp(i)], fp(i));
}
sort(v.begin(), v.end(), greater<pair<ll,int>>());
v.erase(unique(v.begin(),v.end()), v.end());
if (v.size() == 0) {
return D;
}
if (v.size() == 1) {
return max(D, r[center] + l + v[0].first);
}
return max({D, r[center] + l + v[0].first, v[0].first + v[1].first + l + l});
}
/*
12 8 2
0 8 4
8 2 2
2 7 4
5 11 3
5 1 7
1 3 1
1 9 5
10 6 3
18
*/
