#include "dreaming.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int n, m, l;
int far1, far2;
int cnt;
int in[100005];
int out[100005];
int parent[100005];
int dispar[100005];
int maxdist = 0;
bool visited1[100005];
bool visited2[100005];
vector <pair <int, int>> graf[100005];
vector <pair <int, int>> vec;
bool is_parent(int a, int b){
return in[a] <= in[b] && out[b] <= out[a];
}
void dfs1(int v, int dist){
if(dist > maxdist){
far1 = v;
maxdist = dist;
}
in[v] = ++cnt;
visited1[v] = 1;
for(auto par : graf[v]){
int c = par.first;
if(visited1[c]) continue;
parent[c] = v;
dispar[c] = par.second;
dfs1(c, dist + par.second);
}
out[v] = ++cnt;
}
void dfs2(int v, int dist){
if(dist > maxdist){
far2 = v;
maxdist = dist;
}
visited2[v] = 1;
for(auto par : graf[v]){
int c = par.first;
if(visited2[c]) continue;
dfs2(c, dist + par.second);
}
}
void uradi(int i){
far1 = i;
maxdist = 0;
dfs1(i, 0);
maxdist = 0;
far2 = far1;
dfs2(far1, 0);
int minres = maxdist;
int koji = far1;
int x = far2;
int trendist = 0;
while(!is_parent(x, far1)){
trendist += dispar[x];
x = parent[x];
if(max(trendist, maxdist - trendist) < minres){
minres = max(trendist, maxdist - trendist);
koji = x;
}
}
x = far1;
trendist = 0;
while(!is_parent(x, far2)){
trendist += dispar[x];
x = parent[x];
if(max(trendist, maxdist - trendist) < minres){
minres = max(trendist, maxdist - trendist);
koji = x;
}
}
vec.push_back({minres, koji});
}
int travelTime(int N, int M, int L, int A[], int B[], int T[])
{
n = N;
m = M;
l = L;
for(int i=0; i<n; i++){
graf[A[i]+1].push_back({B[i]+1, T[i]});
graf[B[i]+1].push_back({A[i]+1, T[i]});
}
for(int i=1; i<=n; i++){
if(!visited1[i]) uradi(i);
}
sort(vec.begin(), vec.end());
reverse(vec.begin(), vec.end());
for(int i=1; i<vec.size(); i++){
graf[vec[0].second].push_back({vec[i].second, l});
graf[vec[i].second].push_back({vec[0].second, l});
}
for(int i=1; i<=n; i++){
visited1[i] = visited2[i] = 0;
}
maxdist = 0;
far1 = 1;
dfs1(1, 0);
maxdist = 0;
far2 = far1;
dfs2(far1, 0);
return maxdist;
}
