#include<bits/stdc++.h>
#include"dreaming.h"
using namespace std;
const int INF = 1e9 + 1;
vector<vector<pair<int,int>>> adj;
vector<bool> visited;
vector<int> maxdist1;
vector<int> maxdist2;
vector<int> parnode;
int n , m , l;
int curmindist;
void dfs1(int cur) {
visited[cur] = true;
for(auto &x : adj[cur]) {
if(visited[x.first]){
parnode[cur] = x.second;
continue;
}
dfs1(x.first);
if(maxdist1[cur] < maxdist1[x.first] + x.second){
maxdist2[cur] = maxdist1[cur];
maxdist1[cur] =maxdist1[x.first] + x.second;
}
else if(maxdist2[cur] < maxdist1[x.first] + x.second) {
maxdist2[cur] = maxdist1[x.first] + x.second;
}
}
}
//rerouting
void dfs2(int cur,int par){
if(par != -1) {
int tocomp = maxdist1[par] + parnode[cur];
if(maxdist1[cur] + parnode[cur] == maxdist1[par]) {
tocomp = maxdist2[par] + parnode[cur];
}
if(maxdist1[cur] < tocomp){
maxdist2[cur] = maxdist1[cur] ;
maxdist1[cur] = tocomp;
}
else if(maxdist2[cur] < tocomp){
maxdist2[cur] = tocomp;
}
}
for(auto &x : adj[cur]) {
if(x.first == par){
continue;
}
dfs2(x.first, cur);
}
curmindist = min(curmindist, maxdist1[cur]);
}
int travelTime(int N, int M, int L, int A[], int B[], int T[]) {
adj.resize(N);
visited.resize(N);
maxdist1.resize(N);
maxdist2.resize(N);
parnode.resize(N);
for(int i = 0;i < M ;i++) {
adj[A[i]].push_back(pair(B[i], T[i]));
adj[B[i]].push_back(pair(A[i], T[i]));
}
n = N;
m = M;
l = L;
vector<int> v;
for(int i = 0; i < N ; i++) {
if(!visited[i]) {
curmindist = INF;
dfs1(i);
dfs2(i, -1);
v.push_back(curmindist);
}
}
sort(v.rbegin(), v.rend());
int l = (N - 1)/ 2;
int r = l + 1;
int ind = 0;
int maxright = 0;
int maxleft = 0;
int ans = 0;
while(ind < v.size()) {
ans = max(ans, maxleft + v[ind]);
maxright =max(maxright, v[ind] + (r - l) * L);
l--;
ind++;
if(ind < v.size()) {
ans = max(ans , maxright + v[ind]);
maxleft = max(maxleft, v[ind] + (r - l) * L);
r++;
ind++;
}
}
return ans;
}
