#include <bits/stdc++.h>
#include "dreaming.h"
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
#define fi first
#define se second
#define mp make_pair
const int N = (int)1e5 + 100;
vector<pii> T[N];
bool vis[N];
int mx[N];
void dfs(int u, int par){
vis[u]=true;
for(auto x : T[u]){
if(x.fi == par) continue;
dfs(x.fi, u);
mx[u]=max(mx[u], mx[x.fi] + x.se);
}
}
int Q;
int outp = 0;
void dfs1(int u, int par, int in){
Q = min(Q, max(in, mx[u]));
outp = max(outp, mx[u] + in);
pii mx0 = mp(0,-1);
pii mx1 = mp(0,-1);
pii cur;
for(auto x : T[u]){
if(x.fi == par) continue;
cur = mp(mx[x.fi] + x.se, x.fi);
if(cur > mx0){
mx1 = mx0;
mx0 = cur;
}
else if(cur > mx1){
mx1 = cur;
}
}
int send;
for(auto x : T[u]){
if(x.fi == par) continue;
send = in + x.se;
if(x.fi != mx0.se) send = max(send, mx0.fi + x.se);
if(x.fi != mx1.se) send = max(send, mx1.fi + x.se);
dfs1(x.fi, u, send);
}
}
int travelTime(int n, int m, int L, int A[], int B[], int C[]) {
for(int i = 0; i < m ; i ++ ){
T[A[i]].push_back(mp(B[i], C[i]));
T[B[i]].push_back(mp(A[i], C[i]));
}
vector<int> G;
for(int i = 0 ; i < n; i ++ ){
if(vis[i]) continue;
dfs(i, -1);
Q = (int)2e9;
dfs1(i, -1, 0);
G.push_back(Q);
}
sort(G.begin(), G.end());
reverse(G.begin(), G.end());
if(G.size() > 1){
outp = max(outp, G[0] + G[1] + L);
if(G.size() > 2){
outp = max(outp, G[1] + G[2] + L * 2);
}
}
return outp;
}
