#include <bits/stdc++.h>
#include "dreaming.h"
#define X first
#define Y second
#define pii pair<int, int>
#define pb push_back
using namespace std;
const int MN = 100010;
const int INF = 2 * 1e9 + 10;
int n, m, l, ret;
int min_max[MN], c[MN];
int nxt[MN], maxp[MN], h[MN], nxte[MN];
bool mark[MN], bio[MN];
vector<pii> g[MN], v;
vector<int> used;
set<int> s;
bool comp(pii a, pii b){
return a.Y > b.Y;
}
int Find(int x){
if(h[x] == x)
return x;
return h[x] = Find(h[x]);
}
void Union(int x, int y){
h[x] = Find(y);
}
void use(int x){
if(!mark[x]){
used.pb(x);
mark[x] = true;
}
}
int maxPath(int x){
use(x);
bio[x] = true;
maxp[x] = 0;
int mi = x;
for(pair<int, int> e : g[x]){
int y = e.X;
if(bio[y])
continue;
int val = e.Y;
int f = maxPath(y);
if(maxp[y] + val > maxp[x]){
maxp[x] = maxp[y] + val;
mi = f;
nxt[x] = y;
nxte[x] = val;
}
}
return mi;
}
void clearUsed(){
for(int x : used){
nxt[x] = 0;
maxp[x] = 0;
mark[x] = false;
bio[x] = 0;
nxte[x] = 0;
}
used.clear();
}
pii findCenter(int x, bool printp){
clearUsed();
x = maxPath(x);
clearUsed();
int y = maxPath(x);
int p = maxp[x];
ret = max(ret, p);
int zb = 0;
if(printp){
return {p, 0};
}
int mn = p, mni = x;
while(x != y){
if(mn > max(zb, p - zb)){
mn = max(zb, p - zb);
mni = x;
}
zb += nxte[x];
x = nxt[x];
}
if(mn == INF)
mn = 0;
return {mni, mn};
}
int travelTime(int N, int M, int L, int A[], int B[], int T[]){
ios_base::sync_with_stdio(false);
for(int i = 0; i < MN; i++){
h[i] = i;
c[i] = i;
}
n = N;
m = M;
l = L;
for(int i = 0; i < n; i++)
s.insert(i);
for(int i = 0; i < m; i++){
int a, b, t;
a = A[i];
b = B[i];
t = T[i];
g[a].push_back({b, t});
g[b].push_back({a, t});
a = Find(a);
b = Find(b);
s.erase(a);
s.erase(b);
Union(a, b);
s.insert(Find(a));
}
auto it = s.begin();
while(it != s.end()){
pii res = findCenter(*it, 0);
v.pb(res);
it++;
}
sort(v.begin(), v.end(), comp);
if(v.size() > 1)
ret = max(ret, v[0].Y + v[1].Y + l);
if(v.size() > 2)
ret = max(ret, v[1].Y + v[2].Y + l * 2);
return ret;
}
/*
int main(){
int n, m, l;
int a[MN], b[MN], t[MN];
cin >> n >> m >> l;
for(int i = 0; i < m; i++)
cin >> a[i] >> b[i] >> t[i];
cout << travelTime(n, m, l, a, b, t) << "\n";
return 0;
}*/
