//Dreaming
#include<bits/stdc++.h>
#include<dreaming.h>
using namespace std;
constexpr int MAX_N=1e5+9, LOG=17, 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){
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]});
vector<int> spojne;
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];
maks[a].first=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)];
if (maks[a].first<maks[a].second)
swap(maks[a].first, maks[a].second);
spojne.push_back(a);
}
}
int wyn=maks[spojne[0]].first+maks[spojne[0]].second;
for (int i=1; i<spojne.size(); i++){
int a1=maks[spojne[i-1]].first, a2=maks[spojne[i-1]].second, b1=maks[spojne[i]].first, b2=maks[spojne[i]].second;
if (a1==b1){
if (b2<a2)
b1+=L, b2+=L;
else
a1+=L, a2+=L;
}
else if (b1<a1)
b1+=L, b2+=L;
else
a1+=L, a2+=L;
if (a1>b1)
maks[spojne[i]]=make_pair(a1, max(b1, a2));
else
maks[spojne[i]]=make_pair(b1, max(b2, a1));
wyn=max(wyn, maks[spojne[i]].first+maks[spojne[i]].second);
}
return wyn;
}
