#include <bits/stdc++.h>
#include "dreaming.h"
#pragma GCC optimize("O3")
using namespace std;
int n, m, l;
vector< vector< pair<int, int> > > g;
vector<int> maxk;
void furthest(int u, int p, int &f, int &d, int s){
if(s > d) d = s, f = u;
for(auto &t : g[u]){
if(t.first == p) continue;
furthest(t.first, u, f, d, s+t.second);
}
}
void dfs(int u, int p){
maxk[u] = 0;
for(auto &t : g[u]){
if(t.first == p) continue;
dfs(t.first, u);
maxk[u] = max(maxk[u], maxk[t.first]+t.second);
}
}
void dfs2(int u, int p, int o, int &f, int &d){
if(max(o, maxk[u]) < d) d = max(o, maxk[u]), f = u;
vector<int> r;
for(auto &t : g[u]){
if(t.first == p) continue;
r.push_back(t.second+maxk[t.first]);
}
sort(r.rbegin(), r.rend());
for(auto &t : g[u]){
if(t.first == p) continue;
int temp = o+t.second;
if(maxk[t.first]+t.second != r[0]) temp = max(temp, r[0]+t.second);
else if(r.size() > 1) temp = max(temp, r[1]+t.second);
dfs2(t.first, u, temp, f, d);
}
}
int travelTime(int N, int M, int L, int A[], int B[], int T[]){
n = N, m = M, l = L;
g.resize(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]});
}
vector< pair<int, int> > r;
maxk.assign(n, -1);
for(int i = 0; i < n; i++) if(maxk[i] == -1){
dfs(i, -1);
int f, d = 1e9;
dfs2(i, -1, 0, f, d);
r.push_back({d, f});
}
sort(r.rbegin(), r.rend());
for(int i = 1; i < (int)r.size(); i++){
g[r[0].second].push_back({r[i].second, l});
g[r[i].second].push_back({r[0].second, l});
}
int f, d = -1;
furthest(0, -1, f, d, 0);
d = -1;
furthest(f, -1, f, d, 0);
return d;
}
