#include <bits/stdc++.h>
#include "dreaming.h"
using namespace std;
#define pb push_back
#define F first
#define S second
const int N = 1e5+5;
bool mark[N];
int dist[N][2];
vector<pair<int, int>> adj[N];
int mxdep, endnd;
int dst, diam;
void dfs(int node, vector<int>& comp){
comp.pb(node);
mark[node]=1;
for(auto to : adj[node]){
if(!mark[to.F])dfs(to.F, comp);
}
}
void dfs(int node, int dep){
if(dep>mxdep){
endnd=node;
mxdep=dep;
}
mark[node]=1;
for(auto to : adj[node]){
if(!mark[to.F])dfs(to.F, dep+to.S);
}
}
void dfs(int node, int dep, int t){
dist[node][t]=dep;
mark[node]=1;
for(auto to : adj[node]){
if(!mark[to.F])dfs(to.F, dep+to.S, t);
}
}
void finddiameter(int node){
vector<int> comp;
dfs(node, comp);
for(int e : comp)mark[e]=0;
mxdep=0;
int strt=node;
dfs(strt, 0);
strt=endnd;
for(int e : comp)mark[e]=0;
mxdep=0;
dfs(strt, 0);
for(int e : comp)mark[e]=0;
diam=mxdep;
dfs(strt, 0, 0);
for(int e : comp)mark[e]=0;
dfs(endnd, 0, 1);
dst=1e9;
for(int e : comp){
dst=min(dst, max(dist[e][0], dist[e][1]));
}
}
int travelTime(int n, int m, int L, int a[], int b[], int c[]) {
for(int i=0; i< m; i++){
adj[a[i]].pb({b[i], c[i]});
adj[b[i]].pb({a[i], c[i]});
}
vector<int>dsts;
vector<int>diams;
for(int i=0; i< n; i++){
if(!mark[i]){
finddiameter(i);
dsts.pb(dst);
diams.pb(diam);
}
}
int ret=0;
for(int e : diams){
ret=max(ret, e);
}
sort(dsts.begin(), dsts.end());
int sz=dsts.size();
if(sz==1)return ret;
else if(sz==2)return max(ret, L+dsts[1]+dsts[0]);
else return max({ret, L+dsts[sz-1]+dsts[sz-2], 2*L+dsts[sz-2]+dsts[sz-3]});
}
