#include "dreaming.h"
#include <bits/stdc++.h>
using namespace std;
typedef pair<int, int> ii;
typedef vector<pair<int, int>> vii;
typedef vector<int> vi;
typedef long long ll;
#define PB push_back
#define MP make_pair
#define FOR(i, x, y) for (int i = x; i < y ; i ++)
const int MAXN = 1e5 + 5;
int visited[MAXN][2] = { 0 };
int dist[MAXN] = { 0 };
vii adj[MAXN];
int mx_dist = 0;
int mx_node[2];
int parent[MAXN];
void dfs(int curr,int par, int type){
//cout << curr << ' ' << par << " Type: " << type << '\n';
if (visited[curr][type]) return;
if (type == 1) parent[curr] = par;
visited[curr][type] = 1;
for (auto pr : adj[curr]){
if (pr.first == par) continue;
int next = pr.first;
dist[next] = dist[curr] + pr.second;
//cout << "FROM " << curr << " TO " << next << " : " << dist[next] << '\n';
if (dist[next] >= mx_dist){
mx_dist = dist[next];
mx_node[type] = next;
}
dfs(next, curr, type);
}
}
int travelTime(int N, int M, int L, int A[], int B[], int T[]) {
FOR(i, 0, N){
adj[A[i]].PB(MP(B[i], T[i]));
adj[B[i]].PB(MP(A[i], T[i]));
}
vi components;
int inner_dist = 0;
FOR(v, 0, N){
if (visited[v][0]) continue;
// new component
mx_dist = 0;
mx_node[0] = v;
mx_node[1] = v;
dfs(v, -1, 0);
dist[mx_node[0]] = 0;
mx_dist = 0;
dfs(mx_node[0], -1, 1);
//cout <<v << ' ' << mx_node[0] << ' ' << mx_node[1] << ' '<< mx_dist << '\n';
inner_dist = max(inner_dist, mx_dist);
int min_max = mx_dist;
int node = mx_node[1];
int centre = mx_node[1];
while(node != -1){
if (min_max >= max(dist[node], mx_dist - dist[node])){
min_max = max(dist[node], mx_dist - dist[node]);
centre = node;
}
node = parent[node];
}
components.PB(min_max);
}
int temp;
sort(components.rbegin(), components.rend());
if (components.size() == 1){
return inner_dist;
}
else if (components.size() == 2){
temp = max(inner_dist, components[0] + L + components[1]);
return temp;
}
else {
temp = max(inner_dist, components[0] + L + components[1]);
return max(temp, components[1] + 2*L + components[2]);
}
}
