#include "dreaming.h"
#include<bits/stdc++.h>
using namespace std;
int n, m, l;
vector<pair<int, int> > grafo[112345];
vector<int> comp[112345];
int compid[112345];
int altura[112345];
int centro[112345], maxraio[112345];
int marc1[112345], marc2[112345], marc3[112345];
int maxd, maxdi, qtdcomp, cf, cfi;
void dfs1(int x){
marc1[x] = 1;
comp[qtdcomp].push_back(x);
for(int i = 0; i < grafo[x].size(); i++){
int viz = grafo[x][i].first;
if(!marc1[viz]){
altura[viz] = altura[x] + grafo[x][i].second;
if(altura[viz] >= maxd){
maxd = altura[viz];
maxdi = viz;
}
dfs1(viz);
}
}
}
void dfs2(int x){
marc2[x] = 1;
for(int i = 0; i < grafo[x].size(); i++){
int viz = grafo[x][i].first;
if(!marc2[viz]){
altura[viz] = altura[x] + grafo[x][i].second;
maxd = max(maxd, altura[viz]);
dfs2(viz);
}
}
}
bool cmp(int a, int b){
return a > b;
}
void dfs3(int x){
marc3[x] = 1;
for(int i = 0; i < grafo[x].size(); i++){
int viz = grafo[x][i].first;
if(!marc3[viz]){
altura[viz] = altura[x] + grafo[x][i].second;
maxd = max(maxd, altura[viz]);
dfs3(viz);
}
}
}
int ans = 0;
int travelTime(int N, int M, int L, int A[], int B[], int T[]) {
n = N, m = M, l = L;
for(int i = 0; i < m; i++){
//int a, b, t;
//scanf("%d %d", &a, &b, &t);
grafo[A[i]].push_back(make_pair(B[i], T[i]));
grafo[B[i]].push_back(make_pair(A[i], T[i]));
}
//printf("%d\n", n);
for(int i = 0; i < n; i++){
if(!marc1[i]){
maxd = 0;
dfs1(i);
altura[maxdi] = 0;
maxd = 0;
dfs2(maxdi);
int centrodesse = 1e9 + 7, cdi;
for(int j = 0; j < comp[qtdcomp].size(); j++){
if(abs(altura[comp[qtdcomp][j]] - maxd/2) <= centrodesse){
cdi = comp[qtdcomp][j];
centrodesse = abs(altura[comp[qtdcomp][j]] - maxd/2);
}
}
centro[qtdcomp] = cdi;
ans = max(maxd, ans);
maxd = 0;
altura[cdi] = 0;
dfs3(cdi);
maxraio[qtdcomp] = maxd;
qtdcomp++;
}
}
sort(maxraio, maxraio + qtdcomp, cmp);
//printf("%d\n", maxraio[cfi]);
if(qtdcomp > 1){
ans = max(ans, maxraio[0] + maxraio[1] + l);
if(qtdcomp > 2){
ans = max(ans, maxraio[1] + maxraio[2] + 2*l);
}
}
if(n == 1) return 0;
return ans;
}
