#pragma GCC optimize("O1,O2,O3,Ofast,unroll-loops")
#include <bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define pb push_back
typedef long long ll;
typedef pair<int, int> ii;
typedef vector<int> vi;
#include "dreaming.h"
const int MAX = 1e5 + 5;
int N, M, L;
vector<ii> adj[MAX]; // {vertex, dist}
bool vis[MAX];
int timer = 0;
vector<vi> inc; // in component x
vi comp(MAX, -1); // component number
void dfs(int n) {
vis[n] = true;
inc.back().pb(n);
comp[n] = timer;
for (ii x : adj[n]) {
if (!vis[x.fi]) {
vis[x.fi] = true;
dfs(x.fi);
}
}
}
vi dist(MAX, 1e9); // prelim dist
vi dist2(MAX, 1e9); // distance from v1
int fardia = 0;
ii findDia(int n) { // find diameter of component v
queue<int> q;
q.push(inc[n][0]);
dist[inc[n][0]] = 0;
while (!q.empty()) {
int x = q.front();
q.pop();
for (ii y : adj[x]) {
if (dist[y.fi] == 1e9) {
dist[y.fi] = dist[x] + y.se;
q.push(y.fi);
}
}
}
// find farthest among connected
int maxd = -1;
int v1 = -1;
for (int x : inc[n]) {
if (dist[x] > maxd) {
maxd = dist[x];
v1 = x;
}
}
// bfs from v1
// q is already empty
q.push(v1);
dist2[v1] = 0;
while (!q.empty()) {
int x = q.front();
q.pop();
for (ii y : adj[x]) {
if (dist2[y.fi] == 1e9) {
dist2[y.fi] = dist2[x] + y.se;
q.push(y.fi);
}
}
}
maxd = -1;
int v2 = -1;
for (int x : inc[n]) {
if (dist2[x] > maxd) {
maxd = dist2[x];
v2 = x;
}
}
fardia = max(fardia, maxd);
// cout<<"have "<<v1<<" "<<v2<<" "<<maxd<<endl;
return {v1, v2};
}
vi dist3(MAX, 1e9); // distance from v2
int mindist(int n, ii dia) {
queue<int> q;
q.push(dia.se);
dist3[dia.se] = 0;
while (!q.empty()) {
int x = q.front();
q.pop();
for (ii y : adj[x]) {
if (dist3[y.fi] == 1e9) {
dist3[y.fi] = dist3[x] + y.se;
q.push(y.fi);
}
}
}
int minv = 1e9;
for (int x : inc[n]) {
minv = min(minv, max(dist2[x], dist3[x]));
}
return minv;
}
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++) {
adj[A[i]].pb({B[i], T[i]});
adj[B[i]].pb({A[i], T[i]});
}
for (int i = 0; i < N; i++) {
if (!vis[i]) {
inc.pb({});
dfs(i);
timer++;
}
}
int K = inc.size();
/* cout<<"inc: "<<endl;
for (int i = 0; i < K; i++) {
cout<<i<<": ";
for (int x : inc[i])
cout<<x<<" ";
cout<<endl;
}*/
vi allv;
for (int i = 0; i < K; i++) {
ii dia = findDia(i);
// cout<<i<<": "<<dia.fi<<", "<<dia.se<<endl;
int distr = mindist(i, dia);
// cout<<"distr: "<<distr<<endl;
allv.pb(distr);
}
sort(allv.begin(), allv.end(), greater<int>());
/* cout<<"allv: ";
for (int x : allv)
cout<<x<<" ";
cout<<endl;*/
if (M == N - 1) {
return fardia;
}
int ans = fardia;
ans = max(ans, L + allv[0] + allv[1]);
if (M < N - 2)
ans = max(ans, 2 * L + allv[1] + allv[2]);
// for each component, find point that has min farthest dist
return ans;
}
