#include "dreaming.h"
#include<bits/stdc++.h>
#define lf double
#define ll long long
#define ull unsigned ll
#define ii pair<int,int>
#define li pair<ll,int>
#define iii pair<ii,int>
#define iiii pair<ii,ii>
#define iiii2 pair<int,iii>
#define lii pair<ll,ii>
#define lolo pair<ll,ll>
#define heap priority_queue
#define mp make_pair
#define st first
#define nd second
#define pb push_back
#define pf push_front
#define ppb pop_back
#define ppf pop_front
#define all(x) x.begin(),x.end()
#define len(x) strlen(x)
#define sz(x) (int) x.size()
#define orta ((bas+son)/2)
#define min3(x,y,z) min(min(x,y),z)
#define max3(x,y,z) max(max(x,y),z)
#define umin(x,y) x=min(x,y)
#define umax(x,y) x=max(x,y)
#define dbgs(x) cerr<<(#x)<<" --> "<<(x)<<" "
#define dbg(x) cerr<<(#x)<<" --> "<<(x)<<endl;getchar()
#define MOD 1000000007
#define inf 1002000000
#define LOG 20
#define magic 100
#define MAX 100005
#define KOK 350
#define EPS 0.000000000001
#define pw(x) (1<<(x))
#define PI 3.1415926535
using namespace std;
vector< pair<int,short int> > v[MAX];
int mx[4],deep[MAX];
int cnt,Dcnt;
bool vis[MAX];
void up(int val) {
mx[2]=val;
for(int i=2;i>0;i--) {
if(mx[i]>mx[i-1]) swap(mx[i],mx[i-1]);
}
}
void dfs3(int node,int ata) {
deep[node]=0;
for(ii i:v[node]) {
if(i.st==ata) continue ;
dfs3(i.st,node);
if(node==cnt) {
up(deep[i.st]+i.nd);
}
else {
umax(deep[node],deep[i.st]+i.nd);
}
}
}
void dfs2(int node,int ata,int up_max) {
int Mx[2]={0,0};
int MX=max(deep[node],up_max);
if(MX<Dcnt) {
Dcnt=MX;
cnt=node;
}
for(ii i:v[node]) {
if(i.st==ata) continue ;
Mx[1]=max(Mx[1],deep[i.st]+i.nd);
if(Mx[1]>Mx[0]) swap(Mx[1],Mx[0]);
}
for(ii i:v[node]) {
if(i.st==ata) continue ;
int send=(Mx[Mx[0]==deep[i.st]+i.nd]);
dfs2(i.st,node,max(up_max,send)+i.nd);
}
}
void dfs1(int node,int ata) {
deep[node]=0;
vis[node]=true;
for(ii i:v[node]) {
if(i.st==ata) continue ;
dfs1(i.st,node);
umax(deep[node],deep[i.st]+i.nd);
}
}
int travelTime(int N, int M, int L, int A[], int B[], int T[]) {
vector<ii> CMP;
for(int i=0;i<M;i++) {
v[A[i]].pb({B[i],T[i]});
v[B[i]].pb({A[i],T[i]});
}
for(int i=0;i<N;i++) {
if(!vis[i]) {
dfs1(i,-1);
Dcnt=inf;
dfs2(i,-1,0);
// printf("%d %d\n",Dcnt,cnt);
mx[0]=mx[1]=0;
dfs3(cnt,-1);
// printf("%d %d\n",mx[0],mx[1]);
CMP.pb({mx[0],mx[1]});
}
}
int ans=0;
sort(all(CMP),greater<ii>());
mx[0]=mx[1]=-inf;
for(int i=0;i<sz(CMP);i++) {
umax(ans,CMP[i].st+CMP[i].nd);
if(i==0) {
up(CMP[i].st);
}
else {
up(CMP[i].st+L);
}
}
umax(ans,mx[0]+mx[1]);
return ans;
}
/*
int main() {
freopen("read.txt","r",stdin);
int a[55],b[55],t[55],L,N,M;
scanf("%d %d %d",&N,&M,&L);
for(int i=0;i<M;i++) {
scanf("%d %d %d",&a[i],&b[i],&t[i]);
}
printf("%d\n",travelTime(N,M,L,a,b,t));
}*/
