#include "dreaming.h"
#include <bits/stdc++.h>
#define ll int
#define str string
#define ins insert
#define ld long double
#define pb push_back
#define pf push_front
#define pof pop_front()
#define pob pop_back()
#define lb lower_bound
#define ub upper_bound
#define endl "\n"
#define fr first
#define sc second
#define all(x) x.begin(),x.end()
#define rall(x) x.rbegin(),x.rend()
#define sz size()
#define vll vector<ll>
#define bc back()
#define arr array
#define pll vector<pair<ll,ll>>
using namespace std;
template<class S,class T>
bool chmin(S &a,const T &b) {
return a>b?(a=b)==b:false;
}
template<class S,class T>
bool chmax(S &a,const T &b) {
return a<b?(a=b)==b:false;
}
const ll mod=1e9+7;
const ld eps=1e-9;
const ll N=1e5+7;
ll d[N];
vector<set<pair<ll,ll>>> g(N);
ll mx,x;
void dfs(ll v,ll p){
if(chmax(mx,d[v]))x=v;
for(auto i : g[v]){
if(i.fr==p) continue;
d[i.fr]=d[v]+i.sc;
dfs(i.fr,v);
}
}
int travelTime(ll n, ll m, ll l, ll a[], ll b[], ll t[]) {
ll i,j;
set<pair<ll,ll>> st;
for(i=0;i<m;i++){
a[i]++;
b[i]++;
g[a[i]].ins({b[i],t[i]});
g[b[i]].ins({a[i],t[i]});
}
ll ans=0;
for(i=1;i<=n;i++){
if(!d[i]){
mx=0;
dfs(i,0);
mx=0;
d[x]=0;
dfs(x,0);
chmax(ans,mx);
}
}
vll v;
for(i=1;i<=n;i++){
d[i]=0;
if(g[i].sz==0){
v.pb(i);
}else if(g[i].sz==1){
st.ins({g[i].begin()->sc,i});
}
}
while(st.sz){
ll x=st.begin()->sc;
st.erase(st.begin());
for(auto i : g[x]){
g[i.fr].erase(g[i.fr].find({x,i.sc}));
chmax(d[i.fr],d[x]+i.sc);
if(g[i.fr].sz==0)v.pb(i.fr);
else if(g[i.fr].sz==1)st.ins({d[i.fr]+g[i.fr].begin()->sc,i.fr});
}
g[x].clear();
}
for(i=0;i<v.sz;i++) v[i]=d[v[i]];
sort(all(v));
if(v.sz>1)chmax(ans,v.bc+v[v.sz-2]+l);
return ans;
}/*
signed main(){
ll n,m,l;
cin>>n>>m>>l;
ll a[m],b[m],t[m];
for(ll i=0;i<m;i++) cin>>a[i];
for(ll i=0;i<m;i++) cin>>b[i];
for(ll i=0;i<m;i++) cin>>t[i];
cout<<travelTime(n,m,l,a,b,t)<<endl;
}*/
/*
12 8 2
0 8 2 5 5 1 1 10
8 2 7 11 1 3 9 6
4 2 4 3 7 1 5 3
*/
