#include "dreaming.h"
#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define pii pair<int,int>
const int maxn=1e5;
vector<pii> adj[maxn];
int d[maxn][2],d2[maxn],d3[maxn];
bool vis[maxn];
void dfs(int v,int p){
vis[v]=1;
vector<int> z;
for(auto [i,x]:adj[v])if(i!=p){
dfs(i,v);
z.pb(d[i][0]+x);
}
sort(z.rbegin(),z.rend());
for(int i=0;i<z.size()&&i<2;i++)d[v][i]=z[i];
}
void dfs2(int v,int p,int r){
d3[r]=min(d3[r],max(d[v][0],d2[v]));
for(auto [i,x]:adj[v])if(i!=p){
if(d[v][0]==d[i][0]+x){
d2[i]=x+max(d[v][1],d2[v]);
}else{
d2[i]=x+max(d[v][0],d2[v]);
}
dfs2(i,v,r);
}
}
int travelTime(int n, int m, int l, int a[], int b[], int t[]) {
for(int i=0;i<m;i++){
adj[a[i]].pb({b[i],t[i]});
adj[b[i]].pb({a[i],t[i]});
}
vector<int> v;
for(int i=0;i<n;i++){
if(!vis[i]){
dfs(i,-1);
d3[i]=1e9;
dfs2(i,-1,i);
v.pb(d3[i]);
}
}
sort(v.rbegin(),v.rend());
if(v.size()==1){
return v[0];
}else if(v.size()==2){
return v[0]+v[1]+l;
}else{
return max(v[0],v[2]+l)+v[1]+l;
}
}
