#include<bits/stdc++.h>
using namespace std;
#define rep(i,a,b) for(int i=(a); i<(b); ++i)
#define all(array) array.begin(), array.end()
#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> 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);
mx_val[2]=max(mx_val[2],mn);
for(int i=1;i>=0;--i){
if(mx_val[i+1]>mx_val[i]) swap(mx_val[i],mx_val[i+1]);
}
}
}
return max(ans,max(mx_val[0]+mx_val[1]+l,mx_val[1]+mx_val[2]+2*l));
}
