#include <iostream>
#include <algorithm>
#include <queue>
#include <utility>
#include <tuple>
#include "dreaming.h"
using namespace std;
#define ll long long
#define REP(a,i,n) for (int i=a;i<n;i++)
#define f first
#define s second
pair<int, ll> bfs(vector<ll> &distances, int root, vector< vector<pair<int, ll> > > adj) {
queue<int> q;
q.push(root); distances[root] = 0;
ll mx = 0, mxNode=root;
while (q.empty()==false) {
int node = q.front();
q.pop();
if (distances[node] > mx) {
mx = distances[node];
mxNode = node;
}
for (auto [m, x] : adj[node]) {
if (distances[m]!=-1) continue;
distances[m] = distances[node] + x;
q.push(m);
}
}
return make_pair(mxNode, mx);
}
ll lastBFS(vector<ll> &distances, vector<ll> &otherEnd, int root, vector< vector<pair<int, ll> > > adj) {
queue<int> q;
q.push(root); distances[root] = 0;
ll radius=1e10;
while (q.empty()==false) {
int node = q.front();
q.pop();
ll maxDist = max(distances[node], otherEnd[node]);
radius = min(radius, maxDist);
for (auto [m, x] : adj[node]) {
if (distances[m]!=-1) continue;
distances[m] = distances[node] + x;
q.push(m);
}
}
return radius;
}
int travelTime(int N, int M, int L, int A[], int B[], int T[]) {
vector< vector<pair<int, ll> > > adj(N+1);
REP(0,i,M) {
adj[A[i]].emplace_back(B[i], T[i]);
adj[B[i]].emplace_back(A[i], T[i]);
}
vector<pair<int, int>> ends;
vector<ll> dia;
vector<ll> arbiRoot(N+1, -1), distances(N+1, -1);
int end1; ll dist;
REP(0, i, N) {
if (arbiRoot[i]==-1) {
tie(end1, dist) = bfs(arbiRoot, i, adj);
ends.emplace_back(end1, 0);
//cout << "Arbitrary root at " << i << "-> " << dist << " from " << end1 << endl;
}
}
arbiRoot.clear(); arbiRoot.resize(N+1, -1);
REP(0, i, ends.size()) {
if (arbiRoot[ends[i].f]==-1) {
tie(end1, dist) = bfs(arbiRoot, ends[i].f, adj);
ends[i].s = end1;
dia.push_back(dist); //diameter
}
}
vector<ll> radii;
REP(0,i,ends.size()) {
if (distances[ends[i].s]==-1) {
radii.push_back(lastBFS(distances, arbiRoot, ends[i].s, adj));
//cout << "ROOT " << ends[i].s << ": " <<dia[i] << " " << radii[i] << endl;
}
}
ll maxDiameter=0;
for (ll diam : dia) {
maxDiameter = max(maxDiameter, diam);
}
sort(radii.begin(), radii.end(), greater<>());
ll first = radii[0] + radii[1] + L;
ll second = radii[1] + radii[2] + 2*L;
return max(first, max(second, maxDiameter));
}
/*
int main() {
int A[] = {0, 8, 2, 5, 5, 1, 1, 10}, B[] = {8, 2, 7, 11, 1, 3, 9, 6};
int T[] = {4, 2, 4, 3, 7, 1, 5, 3};
cout << travelTime(12,8,2,A,B,T);
return 0;
}*/
