#include "dreaming.h"
#include <bits/stdc++.h>
using namespace std;
using ll=long long;
constexpr int MAXN=1e5+7;
constexpr int INF=1e9+7;
int t[MAXN];
int gl[MAXN];
int odl[MAXN][2];
vector<pair<int,int>> graf[MAXN];
pair<pair<int,int>,int> kraw[MAXN];
vector<int> spojna[MAXN];
int sigma[MAXN][2];
int srodek[MAXN];
int n,m,l;
int Znajdz(int v){
if (v==t[v]) return v;
t[v]=Znajdz(t[v]);
return t[v];
}
void Polacz(int a,int b){
a=Znajdz(a);
b=Znajdz(b);
if (gl[a]>gl[b]) swap(a,b);
t[a]=b;
if (gl[a]==gl[b]) gl[b]++;
}
void DFS(int v,int p,int c,bool x){
if (p==0) odl[v][x]=0;
else odl[v][x]=odl[p][x]+c;
for (pair<int,int> u:graf[v]){
if (u.first==p) continue;
DFS(u.first,v,u.second,x);
}
}
int solve(){
odl[0][0]=-1;odl[0][1]=-1;
for (int i=1;i<=n;i++) t[i]=i;
int a,b,c;
for (int i=0;i<m;i++) Polacz(kraw[i].first.first,kraw[i].first.second);
for (int i=1;i<=n;i++) spojna[Znajdz(i)].push_back(i);
int turbo_srodek=-1;
int mxo=-INF,o;
for (int i=1;i<=n;i++){
if (t[i]!=i) continue;
DFS(i,0,0,0);
for (int v:spojna[i]){
if (odl[v][0]>odl[sigma[i][1]][0]) sigma[i][1]=v;
}
DFS(sigma[i][1],0,0,1);
for (int v:spojna[i]){
if (odl[v][1]>odl[sigma[i][0]][1]) sigma[i][0]=v;
}
DFS(sigma[i][0],0,0,0);
srodek[i]=i;
for (int v:spojna[i]){
if (max(odl[v][0],odl[v][1])<max(odl[srodek[i]][0],odl[srodek[i]][1])) srodek[i]=v;
}
if (mxo<max(odl[srodek[i]][0],odl[srodek[i]][1])){
turbo_srodek=srodek[i];
mxo=max(odl[srodek[i]][0],odl[srodek[i]][1]);
}
}
for (int i=1;i<=n;i++){
if (t[i]!=i) continue;
if (srodek[i]==turbo_srodek) continue;
graf[srodek[i]].push_back({turbo_srodek,l});
graf[turbo_srodek].push_back({srodek[i],l});
}
DFS(1,0,0,0);
a=0;
for (int i=1;i<=n;i++){
if (odl[i][0]>odl[a][0]) a=i;
}
DFS(a,0,0,1);
b=0;
for (int i=1;i<=n;i++){
if (odl[i][1]>odl[b][1]) b=i;
}
return odl[b][1];
}
int travelTime(int _n,int _m,int _l,int _A[],int _B[],int _T[]){
n=_n;m=_m;l=_l;
int a,b,c;
for (int i=0;i<m;i++){
a=_A[i];b=_B[i];c=_T[i];
a++;b++;
graf[a].push_back({b,c});
graf[b].push_back({a,c});
kraw[i]={{a,b},c};
}
return solve();
}
//int main(){
// ios_base::sync_with_stdio(0);
// cin.tie(0);
//}
