#include "dreaming.h"
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define pii pair<int, int>
#define mp make_pair
#define pb push_back
int n, m, l, counter=0;
vector<vector<pii> > graph;
vector<vector<int> > comp;
vector<int> dist, dsu, in, out;
vector<bool> visited;
int fp(int node){
if (dsu[node]==node)return node;
return dsu[node]=fp(dsu[node]);
}
void merge(int a, int b){
int pa=fp(a), pb=fp(b);
dsu[pa]=pb;
}
void dfs(int node, int par, int d){
visited[node]=1;
in[node]=++counter;
dist[node]=d;
for (auto num:graph[node])if (num.first!=par)dfs(num.first, node, d+num.second);
out[node]=counter;
}
bool ispar(int a, int b){
return in[a]<=in[b] && out[a]>=in[b];
}
pii dialen(int node){
pii res;
dfs(node, -1, 0);
int mx=-1, dia1, dia2;
for (auto i:comp[fp(node)]){
if (dist[i]>mx){
mx=dist[i];
dia1=i;
}
}
dfs(dia1, -1, 0);
res.first=-1;
for (auto i:comp[fp(dia1)]){
if (dist[i]>res.first){
res.first=dist[i];
dia2=i;
}
}
res.second=LLONG_MAX;
queue<int> q;
q.push(dia1);
int trav=0, left=res.first;
while (!q.empty()){
int cnode=q.front();
q.pop();
res.second=min(res.second, max(trav, left));
for (auto num:graph[cnode]){
if (ispar(cnode, num.first)&&ispar(num.first, dia2)){
q.push(num.first);
trav+=num.second;
left-=num.second;
}
}
}
return res;
}
signed travelTime(signed N, signed M, signed L, signed A[], signed B[], signed T[]){
n=N, m=M, l=L;
graph.resize(n);
visited.resize(n, 0);
dsu.resize(n, -1);
in.resize(n);
out.resize(n);
dist.resize(n);
comp.resize(n);
for (int i=0; i<n; ++i)dsu[i]=i;
for (int i=0; i<m; ++i){
graph[A[i]].pb(mp(B[i], T[i]));
graph[B[i]].pb(mp(A[i], T[i]));
merge(A[i], B[i]);
}
for (int i=0; i<n; ++i)comp[fp(i)].pb(i);
if (m==n-1)return dialen(0).first;
vector<int> vals, dia;
for (int i=0; i<n; ++i){
if (!visited[i]){
pii res = dialen(i);
dia.pb(res.first);
vals.pb(res.second);
}
}
sort(dia.begin(), dia.end(), greater<int>());
sort(vals.begin(), vals.end(), greater<int>());
if (m==n-2)return max(dia[0], vals[0]+vals[1]+l);
return max(dia[0], max(vals[0]+vals[1]+l, vals[1]+vals[2]+2*l));
}
