//Dreaming
#include<bits/stdc++.h>
#include "dreaming.h"
using namespace std;
constexpr int MAX_N=1e5+9, LOG=18, INF=1e9;
vector<pair<int, int>> drzewo[MAX_N];
bool odw[MAX_N];
int jump[MAX_N][LOG], odl[MAX_N], korzen[MAX_N], gl[MAX_N], maksodl, a, minodl=INF;
pair<int, int> sred[MAX_N], maks[MAX_N];
void dfs(int w, int ojc=0){
jump[w][0]=ojc;
gl[w]=gl[ojc]+1;
for (int i=1; i<LOG; i++)
jump[w][i]=jump[jump[w][i-1]][i-1];
odw[w]=true;
for (auto [new_w, c]:drzewo[w]){
if (!odw[new_w]){
odl[new_w]=odl[w]+c;
if (maksodl<odl[new_w])
maksodl=odl[new_w], a=new_w;
dfs(new_w, w);
}
}
}
void dfs2(int w, int akt=0, int ojc=0){
if (akt>maksodl)
maksodl=akt, a=w;
for (auto [new_w, c]:drzewo[w])
if (new_w!=ojc)
dfs2(new_w, akt+c, w);
}
int lca(int x, int y){
if (gl[x]<gl[y])
swap(x, y);
for (int i=LOG-1; i>=0; i--)
if ((gl[x]-gl[y])>=(1<<i))
x=jump[x][i];
if (x==y)
return x;
for (int i=LOG-1; i>=0; i--)
if (jump[x][i]!=jump[y][i])
x=jump[x][i], y=jump[y][i];
return jump[x][0];
}
void znajdz_korzen(int w, pair<int, int> x, int ojc=0){
int nowa=max(odl[w]+odl[x.first]-2*odl[lca(w, x.first)], odl[w]+odl[x.second]-2*odl[lca(w, x.second)]);
if (nowa<minodl)
minodl=nowa, a=w;
for (auto [new_w, c]:drzewo[w])
if (new_w!=ojc)
znajdz_korzen(new_w, x, w);
}
void ustaw_korzen(int w, int k, int ojc=0){
korzen[w]=k;
for (auto [new_w, c]:drzewo[w])
if(new_w!=ojc)
ustaw_korzen(new_w, k, w);
}
int travelTime(int N, int M, int L, int A[], int B[], int T[]){
for (int i=0; i<M; i++)
drzewo[A[i]+1].push_back({B[i]+1, T[i]}), drzewo[B[i]+1].push_back({A[i]+1, T[i]});
/*
int b, c;
for (int i=0; i<M; i++)
cin >> a >> b >> c, drzewo[a+1].push_back({b+1, c}), drzewo[b+1].push_back({a+1, c});
*/
vector<int> spojne;
int wyn=0;
for (int i=1; i<=N; i++){
if (!odw[i]){
maksodl=0, a=i;
dfs(i);
sred[i].first=a;
maksodl=0, a=i;
dfs2(sred[i].first);
sred[i].second=a;
minodl=INF, a=i;
znajdz_korzen(i, sred[i]);
ustaw_korzen(i, a);
sred[a]=sred[i];
wyn=max(wyn, odl[sred[a].first]+odl[sred[a].second]-2*odl[lca(sred[a].first, sred[a].second)]);
int pom=max(odl[sred[a].first]+odl[a]-2*odl[lca(a, sred[a].first)], maks[a].second=odl[sred[a].second]+odl[a]-2*odl[lca(a, sred[a].second)]);
spojne.push_back(pom);
}
}
sort(spojne.begin(), spojne.end(), greater<int>());
if (spojne.size()>=3)
wyn=max(wyn, spojne[1]+2*L+spojne[2]);
if (spojne.size()>=2)
wyn=max(wyn, spojne[0]+spojne[1]+L);
return wyn;
}
/*
int main(){
int n, m, l; cin >> n >> m >> l;
cout << travelTime(n, m, l);
}
*/
