#include "dreaming.h"
#include <bits/stdc++.h>
using namespace std;
typedef int INT;
#define FOR(i,l,r) for(int i = (l); i < (r); i++)
#define fst first
#define snd second
#define pb push_back
#define mp make_pair
#define V vector
#define int long long
typedef vector<int> vi;
typedef pair<int, int> ii;
typedef vector<vi> vvi;
typedef vector<ii> vii;
const int NMAX = 1e5+10;
struct edge{
int v, l;
};
int N, M;
V<V<edge>> adj;
bitset<NMAX> vis;
void flood(int u){
vis[u] = 1;
for(auto &e : adj[u]) if(!vis[e.v]) flood(e.v);
}
ii furthest(int u, int p){
//cout << "Furthest " << u << " " << p << endl;
ii far = {0, u};
for(edge &e : adj[u]) if(e.v != p) {
ii t = furthest(e.v, u);
t.fst += e.l;
//cout << "cand " << t.fst << " " << t.snd;
far = max(far, t);
}
return far;
}
vi path;
int printpath(int u, int goal, int p, int d = 0){
//cout << u << " " << goal << " " << p << " " << d << endl;
if(u == goal) {path.pb(d); return 1;}
for(auto &e : adj[u]) if(e.v != p) {
if(printpath(e.v, goal, u, d+e.l)) {
path.pb(d);
return 1;
}
}
return 0;
}
INT travelTime(INT n, INT m, INT l, INT A[], INT B[], INT T[]) {
if(n == 1) return 0;
vis.reset();
N = n;
M = m;
int L = l;
adj.resize(N);
FOR(i, 0, M) {
adj[A[i]].pb({B[i], T[i]});
adj[B[i]].pb({A[i], T[i]});
}
vi diams;
vi radii;
//cout<<N<<endl;
//FOR(i, 0, N) cout << vis[i] << endl;
FOR(i, 0, N) if(!vis[i]) {
//cout<<i<<endl;
ii p1 = furthest(i, -1);
ii p2 = furthest(p1.snd, -1);
diams.pb(p2.fst);
//cout << p1.snd << " " << p2.snd << endl;
path.clear();
printpath(p1.snd, p2.snd, -1);
int r = 2e9;
for(int k : path) r = min(r, max(k, p2.fst - k));
radii.pb(r);
flood(i);
}
//for (int d : diams) cout << d << " ";
//cout << endl;
//cout << radii.size() << endl;
sort(radii.begin(), radii.end());
radii[radii.size()-1] -= L;
sort(radii.begin(), radii.end());
//for(int r :radii) cout << r << endl;
int best = radii.back() + radii[radii.size()-2] + 2*L;
for(int d : diams) best = max(d, best);
return best;
}
