#include <bits/stdc++.h>
#include "dreaming.h"
using namespace std;
const int N = 1e5 + 5;
int vis[N], dist[N], par[N], MMM;
vector<pair<int, int>> adj[N];
int D(int u){
dist[u] = 0;
vector<int> C;
queue<int> q;
q.push(u);
C.push_back(u);
while (q.size()){
int v = q.front(); q.pop();
for (auto [i, w] : adj[v]){
if (dist[i] > dist[v] + w){
dist[i] = dist[v] + w;
q.push(i);
C.push_back(i);
}
}
}
int ma = N - 1;
for (auto v : C){
if (dist[v] > dist[ma]) ma = v;
vis[v] = 1;
}
for (auto v : C){
dist[v] = 1e9;
}
dist[ma] = 0;
par[ma] = -1;
q.push(ma);
while (q.size()){
int v = q.front(); q.pop();
for (auto [i, w] : adj[v]){
if (dist[i] > dist[v] + w){
dist[i] = dist[v] + w;
par[i] = v;
q.push(i);
}
}
}
int ans = 1e9, M = N - 1;
for (auto i : C){
if (dist[i] > dist[M]) M = i;
MMM = max(MMM, dist[i]);
}
int MM = M;
// cout << ma << ' ' << MM << endl;
while (M != -1){
ans = min(ans, max(dist[M], dist[MM] - dist[M]));
M = par[M];
}
return ans;
}
int travelTime(int n, int m, int l, int A[], int B[], int T[]) {
for (int i = 0; i < N; i++) dist[i] = 1e9;
dist[N - 1] = -15;
for (int i = 0; i < m; i++){
int u = A[i], v = B[i], w = T[i];
adj[u].push_back({v, w});
adj[v].push_back({u, w});
}
vector<int> dim;
for (int i = 0; i < n; i++){
if (vis[i]) continue;
dim.push_back(D(i));
}
sort(dim.rbegin(), dim.rend());
if (dim.size() == 1){
return MMM;
}
else {
return max(MMM, dim[0] + dim[1] + l);
}
return 0;
}
// int main(){
// int a[] = {0, 8, 2, 5, 5, 1, 1, 10};
// int b[] = {8, 2, 7, 11, 1, 3, 9, 6};
// int t[] = {4, 2, 4, 3, 7, 1, 5, 3};
// cout << travelTime(12, 8, 2, a, b, t);
// }
