#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, mind;
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;
if(altura[viz] >= maxd){
maxd = altura[viz];
maxdi = viz;
};
dfs2(viz);
}
}
}
bool cmp(int a, int b){
return a > b;
}
void dfs3(int x, int d, int type){
marc3[x] = type;
if(type == 1){
altura[x] = d;
}else{
altura[x] = max(altura[x], d);
maxd = max(maxd, altura[x]);
mind = mind == -1 ? altura[x] : min(mind, altura[x]);
}
for(int i = 0; i < grafo[x].size(); i++){
int viz = grafo[x][i].first;
if(marc3[viz] != type){
dfs3(viz, d + grafo[x][i].second, type);
}
}
}
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;
int a = maxdi;
dfs2(maxdi);
int b = maxdi;
int centrodesse = 1e9 + 7, cdi;
mind = -1;
dfs3(a, 0, 1);
dfs3(b, 0 ,2);
ans = max(ans, maxd);
maxraio[qtdcomp] = mind;
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);
}
}
return ans;
}
