#include <bits/stdc++.h>
#include "dreaming.h"
using namespace std;
const int N = 1e5+10;
int n, dist[N];
vector< pair<int,int> > g[N], center;
int mx, sc;
void dfs0(int u, int f, int d) {
dist[u] = d;
if(dist[u] > mx) mx = dist[u], sc = u;
for(auto e : g[u]) if(e.first != f)
dfs0(e.first, u, d + e.second);
}
void dfs1(int u, int f, int d) {
dist[u] = d;
if(dist[u] > mx) mx = dist[u], sc = u;
for(auto e : g[u]) if(e.first != f)
dfs1(e.first, u, d + e.second);
}
void dfs2(int u, int f, int d) {
dist[u] = max(dist[u], d);
if(dist[u] < mx) mx = dist[u], sc = u;
for(auto e : g[u]) if(e.first != f)
dfs2(e.first, u, d + e.second);
}
int travelTime(int N_, int M, int L, int A[], int B[], int T[]) {
n = N_;
for(int i = 0; i < M; i++) {
g[A[i]].push_back({B[i], T[i]});
g[B[i]].push_back({A[i], T[i]});
}
memset(dist,-1,sizeof dist);
for(int i = 0; i < n; i++) {
if(dist[i] == -1) {
mx = -1; dfs0(i,-1,0);
mx = -1; dfs1(sc,-1,0);
mx = (int)2e9; dfs2(sc,-1,0);
center.push_back({-dist[sc], sc});
}
} sort(center.begin(), center.end());
int sz = center.size();
for(int i = 1; i < sz; i++) {
g[center[0].second].push_back({center[i].second, L});
g[center[i].second].push_back({center[0].second, L});
}
memset(dist,-1,sizeof dist);
mx = -1; dfs0(0,-1,0);
mx = -1; dfs1(sc,-1,0);
dfs2(sc,-1,0);
int ans = 0;
for(int i = 0; i < n; i++)
ans = max(ans, dist[i]);
return ans;
}
