#include <bits/stdc++.h>
#include "dreaming.h"
#define ll long long
#define PB push_back
#define F first
#define S second
using namespace std;
const ll MAXN = 100001;
bool recorrido[MAXN];
vector<pair<int, ll > >adj[MAXN];
vector<int>camino;
ll maxtraveltime = 0, nodox;
bool two = false;
ll findlongest(int node, ll cur, int parent){
// cout<<node<<endl;
recorrido[node]=true;
int pp = 0;
for(int i = 0 ;i < adj[node].size(); i++){
if(parent != adj[node][i].F){
if(findlongest(adj[node][i].F, cur+adj[node][i].S, node)){
camino.PB(node);
//cout<<"added "<<node<<" "<<endl;
if(two)pp++;
}
}
}
if(pp)return pp;
if(cur>maxtraveltime){
maxtraveltime=cur;
nodox=node;
camino.PB(node);
//cout<<node<<" ";
return 1;
}
return 0;
}
ll centro, dist1, dist2, diff;
ll findCentro(int node, int lleva){
//cout<<node<<" "<<lleva<<" "<<maxtraveltime-lleva<<endl;
if(llabs((maxtraveltime-lleva) - lleva)<diff){
centro = node;
diff=abs(lleva - (maxtraveltime-lleva));
dist1=lleva;
dist2=maxtraveltime-lleva;
}
if(lleva > (maxtraveltime-lleva)){
return centro;
}
for(int i = 0 ;i < adj[node].size(); i++){
if(camino.back() == adj[node][i].F){
camino.pop_back();
return findCentro(adj[node][i].F, adj[node][i].S+lleva);
}
}
}
int travelTime(int N, int M, int L, int A[], int B[], int T[]) {
for(int i = 0 ; i < M ; i ++){
adj[A[i]].PB({B[i], T[i]});
adj[B[i]].PB({A[i], T[i]});
}
vector<pair<pair<ll, ll>, int> >arboles; //distA distB Centro
for(int i = 0 ; i < N ; i++){
if(!recorrido[i]){
//cout<<"runnin"<<i<<endl;
maxtraveltime=0;
two=false;
diff=LLONG_MAX;
if(adj[i].size()==0){
arboles.PB({{0, 0}, i});
//cout<<"cc"<<0<<" "<<0<<" "<<i<<endl;
continue;
}
findlongest(i, 0, -1);
ll A = nodox;
maxtraveltime = 0;
two=true;
findlongest(A, 0, -1);
ll B = nodox;
////cout<<"mx"<<maxtraveltime<<endl;
camino.pop_back();
ll C = findCentro(A, 0);
arboles.PB({{dist1, dist2}, centro});
//cout<<"cc"<<dist1<<" "<<dist2<<" "<<centro<<endl;
}
}
ll centro1=arboles[0].S, distA=arboles[0].F.F, distB=arboles[0].F.S;
for(int i = 1 ; i < arboles.size() ; i++){
//cout<<centro1<<" "<<distA<<" "<<distB<<endl;
ll unir = L+max(distA, distB)+max(arboles[i].F.F, arboles[i].F.S);
ll ncentro = max(distA, distB)>max(arboles[i].F.F, arboles[i].F.S) ? centro1 : arboles[i].S;
if(max(distA+distB, arboles[i].F.F+arboles[i].F.S)>unir){
if((distA+distB>arboles[i].F.F+arboles[i].F.S)){
//no hay cambio
}else{
centro1=arboles[i].S;
distA=arboles[i].F.F;
distB=arboles[i].F.S;
}
}else{
if(max(distA, distB)>max(arboles[i].F.F, arboles[i].F.S)){
if(distA<distB)swap(distA, distB);
distB=L+max(arboles[i].F.F, arboles[i].F.S);
}else{
if(distA<distB)swap(distA, distB);
distA+=L;
distB=max(arboles[i].F.F, arboles[i].F.S);
}
centro1=ncentro;
}
}
//cout<<centro1<<" "<<distA<<" "<<distB<<endl;
return distA+distB;
}
/*
int main(){
ll n, m, a, b , t, tt;
cin>>n>>m>>tt;
vector<int>A, B, T;
for(int i = 0 ; i < m ; i++){
cin>>a>>b>>t;
A.PB(a);
B.PB(b);
T.PB(t);
}
cout<<travelTime(n, m, tt, A.data(), B.data(), T.data())<<endl;
}
*/
