#include <bits/stdc++.h>
#include "dreaming.h"
using namespace std;
#define INF 1000000000
typedef long long ll;
typedef pair<ll, ll> pi;
vector<vector<pi>> t;
vector<bool> used;
vector<bool> used2;
int n, m, l;
ll d, r;
vector<pi> dist;
vector<int> el;
void dfs1(int u, int p)
{
used[u] = 1;
el.push_back(u);
for (pi v : t[u])
{
if(v.first!=p && !used[v.first])
{
dist[v.first].first = dist[u].first + v.second;
dfs1(v.first, u);
}
}
}
void dfs2(int u, int p)
{
used2[u] = 1;
for (pi v : t[u])
{
if(v.first!=p && !used2[v.first])
{
dist[v.first].second = dist[u].second + v.second;
dfs2(v.first, u);
}
}
}
void dfs3(int u, int p)
{
used2[u] = 1;
for (pi v : t[u])
{
if(v.first!=p && !used2[v.first])
{
dist[v.first].first = dist[u].first + v.second;
dfs3(v.first, u);
}
}
}
bool cmp(pi a, pi b)
{
return (a.second >= b.second);
}
int travelTime(int N, int M, int L, int A[], int B[], int T[])
{
n = N;
m = M;
l = L;
t.resize(n);
used.resize(n, 0);
dist.resize(n, {-1, -1});
used2.resize(n, 0);
for (int i=0; i<m; i++)
{
int x, y, w;
x = A[i];
y = B[i];
w = T[i];
t[x].push_back({y, w});
t[y].push_back({x, w});
}
vector<pi> comp; //diametro massimo e profondità
for (int i=0; i<n; i++)
{
if(!used[i])
{
dist[i].first =0;//parto nodo a caso
el.clear();
dfs1(i, i);
used2.assign(n, 0); //rifaccio dfs
int ind=i, mx = 0;
//cerco nodo a distanza massima
for (int j : el)
{
if(dist[j].first > mx)
{
mx = dist[j].first;
ind = j;
}
}
dist[ind].second = 0;
dfs2(ind, ind);
d = 0;
//trovo diamentro e suoi estremi
for (int j : el)
{
if(dist[j].second > d)
{
d = dist[j].second;
ind = j;
}
}
//rifaccio fs anche su altro estremo
used2.assign(n, 0);
dist[ind].first = 0;
r = INF;
dfs3(ind, ind);
//for (int j : el) //cout<<j<<" "<< dist[j].first<<" "<<dist[j].second<<endl;
for (int j : el)
{
if(dist[j].first==-1) dist[j].first = INF;
if(dist[j].second==-1) dist[j].second = INF;
r = min(r, max(dist[j].first, dist[j].second));
}
comp.push_back({d, r});
}
}
sort(comp.begin(), comp.end(), cmp);
long long res = 0;
for (auto x : comp) res = max(res, x.first);
res = max(res, max(ll(comp[0].second+l+comp[1].second), ll(2*l+comp[1].second+comp[2].second)));
//for (auto x : comp) //cout<< x.first<<" "<<x.second<<endl;
return res;
}
