#include "dreaming.h"
#include <bits/stdc++.h>
#define ad push_back
#define MP make_pair
#define sc second
#define fr first
using namespace std;
const int N = 1e6 + 30;
int n;
vector<pair<int, int> > g[N];
bool col[N];
int dp[N][2], ans;
void dfs0(int v)
{
col[v]=1;
for(auto p : g[v])
{
if(col[p.fr]) continue;
dfs0(p.fr);
dp[v][0] = max(dp[v][0], dp[p.fr][0] + p.sc);
}
}
int dfs(int v)
{
ans = max(ans, dp[v][0] + dp[v][1]);
int ret = max(dp[v][0], dp[v][1]);
col[v]=0;
vector<int> fp;
for(auto p : g[v])
{
if(!col[p.fr]) continue;
dp[p.fr][1] = dp[v][1] + p.sc;
fp.ad(dp[p.fr][0] + p.sc);
}
if(fp.size() > 1)
{
sort(fp.begin(), fp.end());
swap(fp[0], fp[fp.size() - 2]);
for(auto p : g[v])
{
if(!col[p.fr]) continue;
if(dp[p.fr][0] + p.sc == fp.back()) dp[p.fr][1] = max(dp[p.fr][1], p.sc + fp[0]);
else dp[p.fr][1] = max(dp[p.fr][1], p.sc + fp.back());
}
}
for(auto p : g[v])
{
if(!col[p.fr]) continue;
ret = min(ret, dfs(p.fr));
}
return ret;
}
int travelTime(int N, int M, int L, int A[], int B[], int T[])
{
vector <int> fp;
n = N;
for(int i = 0; i < M; i++)
{
g[A[i]].ad(MP(B[i], T[i]));
g[B[i]].ad(MP(A[i], T[i]));
}
for(int i = 0; i < n; i++)
if(!col[i]) dfs0(i);
for(int i = 0; i < n; i++)
if(col[i]) fp.ad(dfs(i));
sort(fp.begin(), fp.end());
reverse(fp.begin(), fp.end());
if(fp.size() > 1)
{
ans = max(ans, fp[0] + fp[1] + L);
if(fp.size() > 2) ans = max(ans, fp[1] + fp[2] + L*2);
}
return ans;
}
