#include <bits/stdc++.h>
#include "dreaming.h"
using namespace std;
int p[100005];
int mxp[100005];
int mxl[100005];
pair<int,int>mxc[100005];
vector<pair<int,int> >v[100005];
int fp(int a){
if(p[a]==a){
return a;
}
return p[a]=fp(p[a]);
}
void un(int a,int b){
p[fp(a)]=fp(b);
}
int mxx=0;
int fmxl(int x,int p){
if(p==-1&&v[x].size()==0){
return 0;
}
if(v[x].size()==1&&p!=-1){
return 0;
}
int se=0,fi=0;
for(int i=0;i<v[x].size();i++){
if(v[x][i].first==p){
continue;
}
int val=fmxl(v[x][i].first,x)+v[x][i].second;
if(val>fi){
se=fi;
fi=val;
}else{
se=max(se,val);
}
}
//cout<<x<<" "<<fi<<" "<<se<<endl;
mxc[x]={fi,se};
if(fi+se>mxx){
mxx=fi+se;
}
return fi;
}
int ans=INT_MAX;
void fmxp(int x,int p,int mp){
int val=max(mp,mxc[x].first);
//cout<<x<<" "<<mp<<" "<<mxc[x].first<<" "<<val<<endl;
ans=min(ans,val);
//cout<<"ans:"<<ans<<endl;
for(int i=0;i<v[x].size();i++){
if(v[x][i].first==p){
continue;
}
//cout<<"before "<<v[x][i].first<<":"<<mp+;
int nmp=max(mp,(mxc[v[x][i].first].first+v[x][i].second==mxc[x].first?mxc[x].second:mxc[x].first))+v[x][i].second;
fmxp(v[x][i].first,x,nmp);
}
}
vector<int>prr;
vector<int>cpmx;
int travelTime(int n, int m, int l, int a[], int b[], int t[]) {
for(int i=0;i<n;i++){
p[i]=i;
}
for(int i=0;i<m;i++){
un(a[i],b[i]);
v[a[i]].push_back({b[i],t[i]});
v[b[i]].push_back({a[i],t[i]});
}
for(int i=0;i<n;i++){
if(p[i]==i){
prr.push_back(i);
}
}
int tmmx=0;
for(int i=0;i<prr.size();i++){
//cout<<prr[i]<<":"<<endl;
mxx=0;
//cout<<"fmxl:"<<prr[i]<<endl;
fmxl(prr[i],-1);
mxl[prr[i]]=mxx;
if(mxx>tmmx){
tmmx=mxx;
}
//cout<<"fmxp:"<<prr[i]<<endl;
ans=INT_MAX;
fmxp(prr[i],-1,0);
mxp[prr[i]]=ans;
cpmx.push_back(ans);
//cout<<mxx<<" "<<ans<<endl;
}
sort(cpmx.begin(),cpmx.end(),greater<int>());
int rans=0;
if(n-m>=2){
rans=max(rans,cpmx[0]+cpmx[1]+l);
}
if(n-m>=3){
rans=max(rans,cpmx[1]+cpmx[2]+l*2);
}
rans=max(rans,tmmx);
return rans;
}
/*
int ar1[100005];
int ar2[100005];
int t1[100005];
int main(){
int n,m,l;
cin>>n>>m>>l;
for(int i=0;i<m;i++){
cin>>ar1[i]>>ar2[i]>>t1[i];
}
cout<<travelTime(n,m,l,ar1,ar2,t1);
}*/
