#include "dreaming.h"
#include <bits/stdc++.h>
using namespace std;
#define ll long long int
const int NN = 1e6 + 5;
vector<pair<int,ll>> adj[NN];
int maxnode;
ll maxdist, tmp, cur, maxxdist;
ll dist[NN],dist2[NN];
int vis[NN],from[NN];
vector<ll> vec;
void dfs(int node, int par)
{
maxdist = max(maxdist, dist[node]);
if(maxdist==dist[node]) maxnode=node;
for(auto to:adj[node])
{
if(to.first==par) continue;
vis[to.first]=1;
dist[to.first]=dist[node]+to.second;
dfs(to.first, node);
}
}
void dfs2(int node, int par)
{
maxdist = max(maxdist, dist2[node]);
if(maxdist==dist2[node]) maxnode=node;
for(auto to:adj[node])
{
if(to.first==par) continue;
from[to.first]=node;
dist2[to.first]=dist2[node]+to.second;
dfs2(to.first, node);
}
}
int travelTime(int N, int M, int L, int A[], int B[], int T[]) {
for(int i=0;i<M;i++)
{
adj[A[i]].push_back({B[i],T[i]});
adj[B[i]].push_back({A[i],T[i]});
}
for(int i=0;i<N;i++)
{
if(vis[i]) continue;
maxdist=0;
dist[i]=0;
vis[i]=1;
dfs(i,i);
from[maxnode]=maxnode;
dist2[maxnode]=0;
maxdist=0;
dfs2(maxnode,maxnode);
maxxdist = max(maxxdist, maxdist);
tmp = maxdist;
cur = maxnode;
while(from[cur]!=cur)
{
tmp = min(tmp, max(maxdist-dist2[cur],dist2[cur]));
cur=from[cur];
}
vec.push_back(tmp);
}
//sort(vec.begin(), vec.end());
cur = vec[vec.size()-1];
for(int i=vec.size()-2;i>=0;i--)
{
maxxdist = max(maxxdist, cur+vec[i]+L);
cur = max(min(cur,vec[i])+L, max(cur,vec[i]));
}
//cout << vec[0] << ' ' << vec[1] << ' ' << vec[2] << ' ' << vec[3] << '\n';
return maxxdist;
/*
if(vec.size()>2) return max({maxxdist, vec[vec.size()-2] + 2ll*L + vec[vec.size()-3], vec[vec.size()-2] + 1ll*L + vec[vec.size()-1]});
return max(maxxdist, vec[vec.size()-2] + 1ll*L + vec[vec.size()-1]);
*/
//if(vec[vec.size()-2]+L<vec[vec.size()-1])return max(maxxdist, vec[vec.size()-1] + 1ll*L + vec[vec.size()-2]);
}
