#include "dreaming.h"
#include <bits/stdc++.h>
using namespace std;
#define forn(i,n) for(int i=0; i<n; ++i)
#define pb push_back
#define all(x) x.begin(), x.end()
#define pi pair<int,int>
#define f first
#define s second
using ll = long long;
struct DSU {
vector<int> p,sz;
DSU(int n) {
forn(i,n) p.pb(i), sz.pb(1);
}
int get(int u) {
return p[u]==u?u:get(p[u]);
}
void uni(int u, int v) {
u=get(u),v=get(v);
if (u==v) return;
if (sz[u]<sz[v]) swap(u,v);
sz[u]+=sz[v];
p[v]=u;
}
};
const int N=1e5+5;
vector<pi> adj[N];
bitset<N> vis;
int d[N], in[N];
void dfs(int u, int p) {
in[u]=0;
for(auto&e:adj[u]) {
int v=e.f, w=e.s;
if (v==p) continue;
d[v]=d[u]+w;
dfs(v,u);
in[u]=max(in[u],in[v]+w);
}
}
int ans=0;
pi find(int u, int p, int o) {
ans=max(ans,o+in[u]);
pi ret = {u, max(o,in[u])};
vector<int> sf={0};
reverse(all(adj[u]));
for(auto&e:adj[u]) {
int v=e.f, w=e.s;
if (v==p) continue;
sf.pb(max(sf.back(),in[v]+w));
}
reverse(all(adj[u]));
int mx=0;
for(auto&e:adj[u]) {
int v=e.f, w=e.s;
if (v==p) continue;
sf.pop_back();
auto x = find(v,u,max({o,mx,sf.back()})+w);
if (x.s<ret.s) ret=x;
mx=max(mx,in[v]+w);
}
return ret;
}
int travelTime(int n, int m, int l, int a[], int b[], int t[]) {
forn(i,m) {
int u=a[i],v=b[i],w=t[i];
adj[u].pb({v,w});
adj[v].pb({u,w});
}
DSU dsu(n);
forn(i,n) for(auto&x:adj[i]) dsu.uni(i,x.f);
vector<int> c;
forn(i,n) {
int u=dsu.get(i);
if (vis[u]) continue;
vis[u]=1;
c.pb(u);
}
int k=c.size();
vector<pi> z;
forn(i,k) {
d[c[i]]=0;
dfs(c[i],-1);
auto q=find(c[i],-1,0);
swap(q.f,q.s);
z.pb(q);
}
sort(all(z));
for (int i=k-2; i>=0; --i) {
int u=z[i].s, v=z[i+1].s;
adj[u].pb({v,l});
adj[v].pb({u,l});
int x=z[i].f, y=z[i+1].f;
assert(x<=y);
z[i] = {max(x+l,y),z[i+1].s};
}
ans=0;
d[0]=0;
dfs(0,-1);
find(0,-1,0);
return ans;
}
