#include<bits/stdc++.h>
using namespace std;
using ll=long long;
using ull=unsigned long long;
#define rep(i,a,b) for(int i=(a); i<(b); ++i)
#define all(array) array.begin(), array.end()
#define bitcnt(x) ((sizeof(x) <= sizeof(int)) ? (32 - __builtin_clz(x)) : (64 - __builtin_clzll(x)))
//#define OJ
#ifndef OJ
#define debug(x) cerr<<"line "<<__LINE__<<": "<<#x<<" "; _print(x); cerr<<'\n';
#else
#define debug(x)
#endif
template<class T> void _print(T a);
template<class T, class V> void _print(pair<T, V> &p);
template<class T> void _print(vector<T> &a);
template<class T> void _print(set<T> &s);
template<class T, class V> void _print(map<T, V> &mp);
template<class T> void _print(deque<T> &d);
template<class T> void _print(stack<T> st);
template<class T> void _print(queue<T> q);
template<class T> void _print(priority_queue<T> pq);
template<class T> void _print(T a){cerr<<a;}
template<class T, class V> void _print(pair<T, V> &p){cerr<<"{"; _print(p.first); cerr<<", "; _print(p.second); cerr<<"}";}
template<class T> void _print(vector<T> &a){cerr<<"[ "; for(auto c:a){_print(c);cerr<<" ";} cerr<<"]";}
template<class T> void _print(set<T> &s){cerr<<"[ "; for(auto c:s){_print(c);cerr<<" ";} cerr<<"]";}
template<class T, class V> void _print(map<T, V> &mp){cerr<<"[ ";for(auto c:mp){_print(c); cerr<<" ";} cerr<<"]";}
template<class T> void _print(deque<T> &d){cerr<<"[ "; for(auto c:d){_print(c); cerr<<" ";} cerr<<"]";}
template<class T> void _print(stack<T> st){cerr<<"| "; while(!st.empty()){auto c=st.top(); st.pop(); _print(c); cerr<<" ";} cerr<<"|";}
template<class T> void _print(queue<T> q){cerr<<"( "; while(!q.empty()){auto c=q.front(); q.pop(); _print(c); cerr<<" ";} cerr<<")";}
template<class T> void _print(priority_queue<T> pq){cerr<<"< ";while(!pq.empty()){auto c=pq.top(); pq.pop(); _print(c); cerr<<" ";} cerr<<">";}
//===============================================================MAIN CODE=============================================================================================
#include "dreaming.h"
int mx,mn;
vector<vector<pair<int,int>>> adj;
vector<int> mx1,mx2,node;
vector<bool> vis;
void dfs1(int u){
vis[u]=1;
for(pair<int,int> &c:adj[u]){
if(vis[c.first]) continue;
dfs1(c.first);
mx2[u]=max(mx2[u],mx1[c.first]+c.second);
if(mx2[u]>mx1[u]){
swap(mx1[u],mx2[u]);
node[u]=c.first;
}
}
}
void dfs2(int u,int p){
for(pair<int, int> &c:adj[u]){
int v,w;
tie(v,w)=c;
if(v==p) continue;
if(v==node[u]){
mx2[v]=max(mx2[v],mx2[u]+w);
if(mx2[v]>mx1[v]){
swap(mx1[v],mx2[v]);
node[v]=u;
}
} else{
mx2[v]=mx1[v];
mx1[v]=mx1[u]+w;
node[v]=u;
}
mx=max(mx,mx1[v]);
mn=min(mn,mx1[v]);
dfs2(v,u);
}
}
int travelTime(int n, int m, int l, int a[], int b[], int t[]) {
adj.resize(n); mx1.resize(n); mx2.resize(n); node.resize(n); vis.resize(n);
int ans=0;
vector<int> val,mx_val(3,-1e9-5);
rep(i,0,m){
adj[a[i]].push_back({b[i],t[i]});
adj[b[i]].push_back({a[i],t[i]});
}
rep(i,0,n){
if(!vis[i]){
dfs1(i);
mx=mx1[i];
mn=mx1[i];
dfs2(i,-1);
ans=max(ans,mx);
val.push_back(mn);
}
}
sort(all(val),greater<int>());
rep(i,0,3){
if(val.size()>i) mx_val[i]=val[i];
}
return max(ans,max(mx_val[0]+mx_val[1]+l,mx_val[1]+mx_val[2]+2*l));
}
