#include "dreaming.h"
#include <bits/stdc++.h>
using namespace std;
struct Edge {
int to, w;
bool operator<(const Edge& other) const {
return w < other.w;
}
};
const int maxN = 1e5 + 5;
const int INF = 1e9 + 5;
int n, m;
vector<Edge> adj[maxN];
vector<int> comp[maxN];
vector<pair<int, int>> centers;
int ccs = 0;
bool vis[maxN];
int dist[maxN];
int par[maxN];
void dfs(int v) {
vis[v] = true;
comp[ccs].push_back(v);
for(Edge u : adj[v]) {
if (!vis[u.to]) {
dfs(u.to);
}
}
}
pair<int, int> mx(int from, int idx) {
priority_queue<Edge> q;
q.push({from, 0});
for(int i : comp[idx]) {
dist[i] = INF;
}
for(int i : comp[idx]) {
par[i] = -1;
}
dist[from] = 0;
while(!q.empty()) {
Edge v = q.top();
q.pop();
if (v.w > dist[v.to]) continue;
for(Edge u : adj[v.to]) {
int d = dist[v.to] + u.w;
if (d < dist[u.to]) {
dist[u.to] = d;
par[u.to] = v.to;
q.push({u.to, dist[u.to]});
}
}
}
pair<int, int> ret = {-1, -1};
for(int i : comp[idx]) {
// cout << i << " " << dist[i] << "\n";
if (dist[i] > ret.second) {
ret = {i, dist[i]};
}
}
assert(ret.second != -1);
assert(ret.second != INF);
return ret;
}
void find_center(int idx) {
int y = mx(comp[idx][0], idx).first;
pair<int, int> p = mx(y, idx);
int z = p.first;
int path = p.second;
int curr = path, center = -1;
for(int i = 0; i < n; i++) {
if (max(dist[z], path-dist[z]) <= curr) {
curr = max(dist[z], path-dist[z]);
center = z;
}
z = par[z];
if (z == -1) break;
}
centers.push_back({curr, center});
}
int travelTime(int N, int M, int L, int A[], int B[], int T[]) {
n = N, m = M;
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]});
}
int sum = 0;
for(int i = 0; i < N; i++) {
if (!vis[i]) {
dfs(i);
find_center(ccs);
ccs++;
}
}
sort(centers.rbegin(), centers.rend());
for(int i = 1; i < (int) centers.size(); i++) {
adj[centers[0].second].push_back({centers[i].second, L});
adj[centers[i].second].push_back({centers[0].second, L});
// cout << centers[0].second << " " << centers[i].second << "\n";
}
for(int i = 1; i < ccs; i++) {
for(int j : comp[i]) {
comp[0].push_back(j);
}
}
return mx(mx(0, 0).first, 0).second;
}
