#include "dreaming.h"
#include <bits/stdc++.h>
#include <vector>
using namespace std;
int n;
const int mxN = 1e5 + 12;
bool vis[mxN];
int dep[mxN];
pair<int, int> iznad[mxN];
vector<pair<int, int>> adj[mxN];
void dfs(int s, int p = -1) {
vis[s] = true;
if(p == -1) {
dep[s] = 0;
} else {
dep[s] = dep[p] + 1;
}
for(auto iv : adj[s]) {
int e = iv.first;
int w = iv.second;
if(e == p) continue;
iznad[e] = make_pair(s, w);
dfs(e, s);
}
}
int dist[mxN];
vector<int> posetili;
void dfsNajdalji(int s, int p = -1) {
if(p == -1) {
dist[s] = 0;
}
posetili.push_back(s);
for(auto iv : adj[s]) {
int e = iv.first;
int w = iv.second;
if(e == p) continue;
dist[e] = dist[s] + w;
dfsNajdalji(e, s);
}
}
int nadjiNajdalji(int s) {
posetili.clear();
dfsNajdalji(s);
pair<int, int> p{-1, -1};
for(auto i : posetili) {
pair<int, int> temp{dist[i], i};
p = max(p, temp);
}
return p.second;
}
pair<int, int> putanja(int a, int b) {
int pocA = a;
int pocB = b;
// for(int i = 0; i < n; ++i) {
// cerr << i << " " << dep[i] << endl;
// }
if(dep[a] < dep[b]) swap(a, b); //dep[a] >= dep[b]
int suma = 0;
while(dep[a] > dep[b]) {
// cerr << a << " " << b << endl;
suma += iznad[a].second;
a = iznad[a].first;
}
while(a != b) {
suma += iznad[a].second;
suma += iznad[b].second;
a = iznad[a].first;
b = iznad[b].first;
}
int rodjak = a;
a = pocA;
b = pocB;
int odg = int(1e9 + 12);
int trenutno = 0;
odg = suma;
// if(a == rodjak && b == rodjak) {
// odg = 0;
// }
// cerr << a << " " << rodjak << endl;
// cerr << b << " " << rodjak << endl;
while(a != rodjak) {
odg = min(odg, max(trenutno, suma - trenutno));
trenutno += iznad[a].second;
a = iznad[a].first;
}
odg = min(odg, max(trenutno, suma - trenutno));
trenutno = 0;
while(b != rodjak) {
odg = min(odg, max(trenutno, suma - trenutno));
trenutno += iznad[b].second;
b = iznad[b].first;
}
odg = min(odg, max(trenutno, suma - trenutno));
return make_pair(suma, odg);
}
int travelTime(int N, int M, int L, int A[], int B[], int T[]) {
n = N;
for(int i = 0; i < M; ++i) {
int u = A[i];
int v = B[i];
int w = T[i];
adj[u].push_back({v, w});
adj[v].push_back({u, w});
}
vector<int> svi;
int ans = 0;
for(int i = 0; i < n; ++i) {
if(!vis[i]) {
dfs(i);
int a = nadjiNajdalji(i);
int b = nadjiNajdalji(a);
auto odg = putanja(a, b);
svi.push_back(odg.second);
ans = max(ans, odg.first);
// cerr << odg.first << " " << odg.second << endl;
}
}
sort(svi.rbegin(), svi.rend());
if(svi.size() > 1) {
ans = max(ans, svi[0] + svi[1] + L);
}
return ans;
}
