#include "dreaming.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef vector<int> vi;
typedef pair<int, int> ii;
typedef vector<ii> vii;
typedef long double ld;
typedef vector<vector<ll>> vll;
#define FOR(i, a, b) for(int i = a; i < b; i++)
#define ROF(i, a, b) for(int i = a; i >= b; i--)
#define pb push_back
#define ms memset
#define fi first
#define se second
struct segtree{
vi tl, tr, mx, op; int sz;
void build(int v, int l, int r){
tl[v]=l; tr[v]=r;
if (l==r) return;
int tm = (l+r)/2;
build(2*v,l,tm); build(2*v+1,tm+1,r);
}
void init(int n){
sz=n;
tl.assign(4*n,0); tr.assign(4*n,0);
mx.assign(4*n,0); op.assign(4*n,0);
build(1,0,n-1);
}
void prop(int v){
if (tl[v]==tr[v]){op[v]=0; return;}
int tm = (tl[v]+tr[v])/2;
op[2*v] += op[v]; mx[2*v] += op[v];
op[2*v+1] += op[v]; mx[2*v+1] += op[v];
op[v] = 0;
}
void upd(int v, int l, int r, int val){
//prop(v);
if (tl[v]==l && tr[v]==r){
op[v] += val; mx[v] += val;
return;
}
if (l>r) return;
int tm = (tl[v]+tr[v])/2;
upd(2*v,l,min(r,tm),val);
upd(2*v+1,max(l,tm+1),r,val);
mx[v] = max(mx[2*v],mx[2*v+1]) + op[v];
}
};
const int mxn = 1e5+1;
vii g[mxn];
vi p(mxn), dist(mxn), tin(mxn), sz(mxn);
vi mx_dist(mxn);
vi CC[mxn]; int cc_num = 0;
int cur = 0;
void dfs(int u){
CC[cc_num].pb(u);
tin[u] = cur; cur++;
sz[u] = 1;
for (ii e : g[u]){
int v = e.fi;
if (p[u] == v) continue;
dist[v] = dist[u] + e.se; p[v] = u;
dfs(v);
sz[u] += sz[v];
}
}
segtree st;
int n;
void get_mx(int u){
mx_dist[u] = st.mx[1];
for (ii e : g[u]){
int v = e.fi, w = e.se;
if (p[u]==v) continue;
st.upd(1,0,tin[v]-1,w); st.upd(1,tin[v],tin[v]+sz[v]-1,-w); st.upd(1,tin[v]+sz[v],n-1,w);
get_mx(v);
st.upd(1,0,tin[v]-1,-w); st.upd(1,tin[v],tin[v]+sz[v]-1,w); st.upd(1,tin[v]+sz[v],n-1,-w);
}
}
int travelTime(int N, int M, int L, int A[], int B[], int T[]) {
n = N;
vi used(N);
int ans = 0;
vi costs;
FOR(i,0,M){
g[A[i]].pb({B[i],T[i]}); g[B[i]].pb({A[i],T[i]});
}
FOR(i,0,N){
if (used[i]) continue;
used[i] = 1; cc_num++;
cur = 0;
dfs(i); st.init(sz[i]); n = sz[i];
FOR(j,0,sz[i]){
int v = CC[cc_num][j]; used[v]=1;
st.upd(1,tin[v],tin[v],dist[v]);
}
get_mx(i);
int mn = mx_dist[i];
FOR(j,0,sz[i]){
int v = CC[cc_num][j];
mn = min(mn, mx_dist[v]);
}
costs.pb(mn);
}
FOR(i,0,N) ans = max(ans, mx_dist[i]);
sort(costs.rbegin(), costs.rend());
if (N-M==1) return ans;
if (N-M==2) return max(ans,L + costs[0] + costs[1]);
return max(ans,max(L+costs[0]+costs[1],2*L+costs[1]+costs[2]));
}
