#include "dreaming.h"
#include <vector>
#include <iostream>
#include <queue>
using namespace std;
#define pii pair<int,int>
#define fst first
#define snd second
#define vpi vector<pii>
#define pub push_back
int n,m,l,dp[100001][2]={},mn = 1e9,rs = 0;
bool bt[100001]={};
priority_queue<int> pq;
vector<vpi> adj;
inline void dfs(int u,int p)
{
bt[u] = 1;
for (auto v:adj[u])
{
if (v.fst!=p)
{
dfs(v.fst,u);
if (dp[v.fst][0] + v.snd > dp[u][0])
{
dp[u][1] = dp[u][0];
dp[u][0] = dp[v.fst][0] + v.snd;
}
else if (dp[v.fst][0] + v.snd > dp[u][1])
{
dp[u][1] = dp[v.fst][0] + v.snd;
}
}
}
}
inline void dfs2(int u,int p,int mx)
{
mn = min(mn,max(mx,dp[u][0]));
rs = max(rs,dp[u][0] + max(dp[u][1],mx));
for (auto v:adj[u])
{
if (v.fst!=p)
{
bt[u] = 1;
dfs2(v.fst,u,max(mx,(dp[u][0]==dp[v.fst][0] + v.snd)?dp[u][1]:dp[u][0]) + v.snd);
}
}
}
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<n;i++) {adj.pub(vpi());}
for (int i=0;i<m;i++)
{
adj[A[i]].pub({B[i],T[i]});
adj[B[i]].pub({A[i],T[i]});
}
for (int i=0;i<n;i++)
{
if (!bt[i])
{
dfs(i,-1);
dfs2(i,-1,0);
//cout<<i<<" "<<mn<<"\n";
pq.push(mn);
mn = 1e9;
}
}
if (pq.size()>2)
{
int a = pq.top();pq.pop();
int b = pq.top();pq.pop();
int c = pq.top();pq.pop();
rs = max(rs,max(a + b + l,b + c + 2*l));
}
else if (pq.size()>1)
{
int a = pq.top();pq.pop();
int b = pq.top();pq.pop();
rs = max(rs,a + b + l);
}
return rs;
}
