#include <bits/stdc++.h>
#include "dreaming.h"
using namespace std;
const int INF = 2e9;
using pii = pair<int, int>;
void Max (pair<pii, pii> &b, pii a)
{
if(b.first < a)
{
b.second = b.first;
b.first = a;
}
else if(b.second < a)
{
b.second = a;
}
}
int travelTime(int N, int M, int L, int A[], int B[], int T[])
{
int n = N;
vector<vector<pii>> g(n);
for(int i = 0 ; i < M ; i++)
{
g[A[i]].push_back({B[i], T[i]});
g[B[i]].push_back({A[i], T[i]});
}
vector<pair<pii, pii>> mm(n);
vector<bool> flag(n);
function<int(int, int)> dfs1 = [&](int nod, int father)
{
flag[nod] = true;
for(auto i: g[nod])
{
if(i.first != father)
{
Max(mm[nod], {dfs1(i.first, nod) + i.second, i.first});
}
}
return mm[nod].first.first ;
};
for(int i = 0 ; i < n ; i++)
{
if(!flag[i])
{
dfs1(i, -1);
}
}
//for(auto i: mm)
// cout << i.first.first << ' ' << i.first.second << ' ' << i.second.first << ' ' << i.second.second << endl ;
function<int(int, int, int)> dfs2 = [&](int nod, int father, int path)
{
flag[nod] = true;
int ans = max(mm[nod].first.first, path);
for(auto i: g[nod])
{
if(i.first != father)
{
int tempPath = path;
if(i.first == mm[nod].first.second)
tempPath = max(tempPath, mm[nod].second.first);
else
tempPath = max(tempPath, mm[nod].first.first);
ans = min(ans, dfs2(i.first, nod, tempPath + i.second));
}
}
return ans;
};
flag = vector<bool> (n, false);
vector<int> vans;
for(int i = 0 ; i < n ; i++)
{
if(!flag[i])
vans.push_back(dfs2(i, -1, 0));
}
//for(auto i: vans)
// cout << i << ' ' ;
//cout << endl ;
int ans = 0;
for(auto i: mm)
ans = max(ans, i.first.first + i.second.first);
if(vans.size() <= 1)
return ans;
else
{
sort(vans.rbegin(), vans.rend());
ans = max(ans, vans[0] + vans[1] + L);
if(vans.size() >= 3)
ans = max(ans, vans[1] + vans[2] + 2 * L);
return ans;
}
}
