#include "dreaming.h"
#include <bits/stdc++.h>
using namespace std;
int maksi = 0;
vector<vector<pair<int, int>>> graf;
vector<bool> odw, odw2;
vector<int> tab, dlg1, dlg2;
void dfs(int x){
odw[x] = true;
dlg1[x] = 0;
dlg2[x] = 0;
for(auto it:graf[x]){
if(!odw[it.first]){
dfs(it.first);
int tmp = it.second+dlg1[it.first];
if(tmp>dlg2[x]){
if(tmp>dlg1[x]){
dlg2[x]=dlg1[x];
dlg1[x] = tmp;
}else{
dlg2[x] = tmp;
}
}
}
}
}
int dfs2(int x, int gor = 0){
odw2[x] = true;
int out = 1e9;
for(auto it:graf[x]){
if(!odw2[it.first]){
if(dlg1[it.first]+it.second!=dlg1[x]) out = min(out, dfs2(it.first, max(gor, dlg1[x])+it.second));
else out = min(out, dfs2(it.first, max(gor, dlg2[x])+it.second));
}
}
int cur = dlg1[x];
cur = max(cur, gor);
out = min(out, cur);
maksi = max(maksi, max(dlg1[x]+dlg2[x], dlg1[x]+gor));
return out;
}
int travelTime(int N, int M, int L, int A[], int B[], int T[]) {
odw.resize(N);
odw2.resize(N);
graf.resize(N);
dlg1.resize(N);
dlg2.resize(N);
for(int i = 0; i < M; i++){
graf[A[i]].push_back(make_pair(B[i], T[i]));
graf[B[i]].push_back(make_pair(A[i], T[i]));
}
for(int i = 0; i < N; i++){
if(!odw[i]){
dfs(i);
tab.push_back(dfs2(i));
}
}
sort(tab.begin(), tab.end());
if(tab.size()==1) return max(maksi, tab.back());
if(tab.size()==2) return max(maksi, tab[0]+tab[1]+L);
return max(maksi, max(tab.back()+L+tab[tab.size()-2], tab[tab.size()-2]+tab[tab.size()-3]+2*L));
}
