#include "dreaming.h"
//ᴇᴀᴄʜ ᴘᴇʀꜱᴏɴ ᴡɪʟʟ ᴏɴʟʏ ʜᴀᴠᴇ ᴡʜᴀᴛ ᴛʜᴇʏ ᴇɴᴅᴇᴀᴠᴏᴜʀᴇᴅ ᴛᴏᴡᴀʀᴅꜱ [53:39]
//Author: Sazid Hasan
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef double dl;
typedef vector<int> vi;
typedef vector<vector<int>> vii;
typedef vector<ll> vl;
typedef vector<bool> vb;
typedef pair<int,int> pii;
typedef pair<ll, ll> pll;
#define ff first
#define ss second
#define all(a) a.begin(),a.end()
#define gcd(a,b) __gcd(a,b)
#define lcm(a,b) (a*(b/gcd(a,b)))
#define spc " "
#ifdef ONLINE_JUDGE
#define debarr(array)
#define deb(x)
#define del
#else
#define debarr(array) for(int w = 0; w < array.size(); w++) cerr << #array << "-" << w << " = " << array[w] << endl;
#define deb(x) cerr << #x << " = " << x << endl;
#define del cerr << '\n';
#endif
const double PI = acos(-1);
const int MOD = 1000000007;
const int inf = (2147483647);
// const int MAXN = 15;
const int MAXN = 1e5+10;
vector<vector<pii>> adj(MAXN);
vector<pll> dp(MAXN, {0, 0});
vector<bool> visited(MAXN);
ll mx = 0;
void setMx(pll &a, ll &b){
if(b>a.ff){
swap(a.ff, a.ss);
swap(a.ff, b);
}else if(b>a.ss){
swap(a.ss, b);
}
return;
}
void mxDist(int i, int p = -1){
visited[i] = 1;
for(auto x: adj[i]){
if(x.ff!=p){
mxDist(x.ff, i);
ll now = dp[x.ff].ff + x.ss;
setMx(dp[i], now);
}
}
}
void reroot(int i, ll &mn, ll d = 0, int p = -1){
visited[i] = 1;
setMx(dp[i], d);
// deb(i)
// deb(dp[i].ff)
// deb(dp[i].ss) del
mn = min(dp[i].ff, mn);
mx = max(dp[i].ff, mx);
for(auto x: adj[i]){
if(x.ff==p) continue;
if(x.ss+dp[x.ff].ff==dp[i].ff){
reroot(x.ff, mn, dp[i].ss+x.ss, i);
}else{
reroot(x.ff, mn, dp[i].ff+x.ss, i);
}
}
}
int travelTime(int N, int M, int L, int A[], int B[], int T[]) {
for(int i = 0; i < M; i++){
adj[A[i]].push_back({B[i], T[i]});
adj[B[i]].push_back({A[i], T[i]});
}
for(int i = 0; i < N; i++){
if(!visited[i]) mxDist(i);
}
visited.assign(N+5, 0);
vl mns;
for(int i = 0; i < N; i++){
if(!visited[i]){
ll m = 1LL<<60;
reroot(i, m);
mns.push_back(m);
}
}
sort(all(mns), greater<ll>());
// for(int i = 0; i < N; i++) cerr << i << " = " << dp[i].ff << spc << dp[i].ss << '\n';
if(mns.size()==1) return mx;
if(mns.size()==2) return (mns[0]+mns[1]+L);
ll ans = mns[0]+mns[1]+L;
ans = max(mns[2]+mns[1]+L+L, ans);
return ans;
}
