#include "dreaming.h"
#include <bits/stdc++.h>
using namespace std;
#define fi first
#define se second
const int LIM = 1e5 + 5;
vector <pair <int, int>> adj[LIM];
int dist[LIM];
void add_edge(int u, int v, int w) {
adj[u].emplace_back(v, w);
adj[v].emplace_back(u, w);
// cerr << u << ' ' << v << ' ' << w << '\n';
}
// sub4
void dfs(int u, int p = -1) {
for (auto [v, w]: adj[u]) if (v != p) {
dist[v] = dist[u] + w;
dfs(v, u);
}
}
int sub4(int N, int M, int L, int A[], int B[], int T[]) {
int root = -1, v = -1, ma = 0;
vector <bool> alone(N, true);
for (int i = 0; i < M; i++) {
if (T[i] > ma) root = A[i], v = B[i], ma = T[i];
alone[A[i]] = alone[B[i]] = false;
}
for (int i = 0; i < M; i++) {
add_edge(A[i], B[i], T[i]);
}
for (int i = 0; i < N; i++) {
if (alone[i]) add_edge(root, i, L);
}
for (int i = 0; i < M; i++) {
if (A[i] != root && B[i] != root)
add_edge(root, A[i], L);
}
dfs(root); int leaf = -1, maDis = 0;
for (int i = 0; i < N; i++)
if (maDis < dist[i]) {
maDis = dist[i];
leaf = i;
}
dist[leaf] = 0; dfs(leaf);
return *max_element(dist, dist + N);
}
//
// sub5
int D[3005][3005], f[3005], id[3005];
void findDist(int root, int u, int p) {
id[u] = id[root];
for (auto [v, w]: adj[u]) if (v != p) {
D[root][v] = D[root][u] + w;
findDist(root, v, u);
}
}
int sub5(int N, int M, int L, int A[], int B[], int T[]) {
for (int i = 0; i < M; i++)
add_edge(A[i], B[i], T[i]);
memset(D, -1, sizeof D);
memset(id, -1, sizeof id);
int tree = -1;
for (int i = 0; i < N; i++) {
if (id[i] == -1) id[i] = ++tree;
D[i][i] = 0; findDist(i, i, -1);
f[i] = *max_element(D[i], D[i] + N);
}
vector <int> miDist(tree + 1, 2e9), dia(tree + 1, 0);
for (int i = 0; i < N; i++) {
miDist[id[i]] = min(miDist[id[i]], f[i]);
dia[id[i]] = max(dia[id[i]], f[i]);
}
int init = *max_element(dia.begin(), dia.end());
// diameter per tree
int ans = 2e9;
for (int center = 0; center < N; center++) {
pair <int, int> ma(f[center], 0);
for (int t = 0; t <= tree; t++) if (t != id[center]) {
int cur = miDist[t] + L;
if (cur > ma.fi) ma = make_pair(cur, ma.fi);
else ma.se = max(ma.se, cur);
}
int res = max(init, ma.fi + ma.se);
ans = min(ans, res);
}
return ans;
}
//
int travelTime(int N, int M, int L, int A[], int B[], int T[]) {
if (N <= 3000) return sub5(N, M, L, A, B, T);
else return sub4(N, M, L, A, B, T);
}
