#include "dreaming.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define vc vector
typedef vc<ll> vcll;
#define pr pair
typedef pr<ll, ll> prll;
#define umap unordered_map
#define f0r(i,a,n) for (i=(a); i<(n); i++)
#define f1r(i,a,n) for (i=(a); i<=(n); i++)
#define r0f(i,n,a) for (i=(n); i>(a); i--)
#define r1f(i,n,a) for (i=(n); i>=(a); i--)
#define fi first
#define se second
#define pb push_back
#define mp make_pair
#define in(s, x) ((s).find((x)) != (s).end())
#define all(x) (x).begin(), (x).end()
#define allrev(x) (x).rbegin(), (x).rend()
inline void maxa(ll &a, ll b) { if (a<b) a=b; }
inline void mina(ll &a, ll b) { if (a>b) a=b; }
#define INF (LLONG_MAX>>2ll)
#define mxN 100'010ll
ll n, m, l;
int *uar, *var, *war;
vc<vc<prll>> gr(mxN); // fi is w, se is v
vc<prll> par(mxN);
vcll f;
inline void build_gr()
{
ll i;
f0r(i,0,m)
{
ll u, v, w;
u=uar[i];
v=var[i];
w=war[i];
gr[u].pb({w, v});
gr[v].pb({w, u});
}
}
vc<bool> seen(mxN, 0);
vcll whole(mxN); // whole
vcll comp; // comp for component
void dfs(ll u) // makes tree // good
{
if (seen[u]) return;
seen[u]=1;
comp.pb(u);
for (prll edge : gr[u])
{
ll v=edge.se;
if (seen[v]) continue; // is par
ll w=edge.fi;
par[v]={w, u};
dfs(v);
}
}
ll calc_cnt=0;
ll clutch_cnt=0;
ll calc_whole(ll u)
{
ll m=0; // max
for (prll edge : gr[u])
{
ll v=edge.se;
ll w = edge.fi;
maxa(m, calc_whole(v) + w);
}
return whole[u]=m;
}
vc<umap<ll, ll>> max_except(mxN);
void build_except(ll u, vc<prll> &ar) // fi is node, se is max
{
ll i;
ll n=ar.size();
/*
printf("bulid_except of u: %lli\n", u);
printf("ar: ");
f0r(i,0,n) printf("{%lli, %lli} ", ar[i].se, ar[i].fi);
printf("\n");
*/
vcll sma(n+10); // max, incl., sma[n]==0
sma[n]=0;
r1f(i,n-1, 0) sma[i]=max(sma[i+1], ar[i].fi);
/*
printf("sma: ");
f0r(i,0,n) printf("%lli ", sma[i]);
printf("\n");
*/
ll rm=0; // running max
f0r(i,0,n)
{
max_except[u][ar[i].se] = max(rm, sma[i+1]);
// printf("rm: %lli\n", rm);
// printf("value of %lli: %lli\n", ar[i].se, max(rm, sma[i+1]));
maxa(rm, ar[i].fi);
}
sma.clear();
}
void build_ar_root(ll u)
{
vc<prll> ar;
for (prll edge : gr[u])
{
ll v=edge.se;
ll w=edge.fi;
ar.pb({whole[v]+w, v});
}
build_except(u, ar);
ar.clear();
}
ll root;
ll gm;
ll dfs_calc_real(ll u)
{
ll m=whole[u]; // max
if (u==root)
{
for (prll edge : gr[u])
{
ll v = edge.se;
mina(gm, dfs_calc_real(v));
}
return m;
}
// u!=root
vc<prll> ar;
for (prll edge : gr[u])
{
ll v = edge.se;
ll w = edge.fi;
ar.pb({whole[v]+w, v});
}
ll p=par[u].se;
ll w=par[u].fi;
ll v = max_except[p][u];
maxa(whole[u], w+v);
ar.pb({w+v, p});
m=whole[u];
build_except(u, ar);
ar.clear();
for (prll edge : gr[u])
{
ll v = edge.se;
mina(gm, dfs_calc_real(v));
}
return m;
}
inline void remake_gr()
{
for (ll u : comp) for (prll &edge : gr[u])
{
ll v=edge.se;
if (par[u].se==v)
{
edge=gr[u][gr[u].size()-1];
gr[u].pop_back();
}
}
}
inline ll minmaxdist(ll u)
{
comp.clear();
root=u;
par[root]={0, -1};
dfs(u); // good
remake_gr(); // bad
// printf("comp.size: %lli\n", (ll)comp.size());
calc_whole(u); // prob works
build_ar_root(u);
gm=INF;
ll t = dfs_calc_real(u); // min
mina(gm, t);
// printf("m: %lli, on u: %lli\n", m, u);
return gm;
}
inline void build_ar()
{
ll u;
f0r(u,0,n)
{
if (seen[u]) continue;
// printf("WPAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA, u: %lli\n", u);
f.pb(minmaxdist(u));
}
}
inline ll value()
{
ll z=f.size();
ll m=-1; // max
/*
printf("z: %lli\n", z);
printf("f: ");
for (ll v : f) printf("%lli ", v);
printf("\n");
*/
if (z==1) m = f[0];
else if (z==2) m = f[0]+f[1]+l;
else m = max(f[0]+f[1]+l, f[1]+f[2]+(2*l));
ll u;
f0r(u,0,n) maxa(m, whole[u]);
return m;
}
int travelTime(int N, int M, int L, int A[], int B[], int T[])
{
n=N;
m=M;
l=L;
uar=A;
var=B;
war=T;
build_gr();
build_ar(); // slow
sort(allrev(f));
return value();
}
