#define F first
#define S second
#define rep(i,a,b) for(int i=a;!(a==b&&i!=b)&&((i<=b&&b>=a)||(i>=b&&a>=b));i+=(a<=b?1:-1))
#define pb push_back
#define Fbitl __builtin_ffs
#define bit1 __builtin_popcount
#include <iostream>
#include <math.h>
#include <algorithm>
#include <string.h>
#include <vector>
#include <queue>
#include <map>
#include <unordered_map>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef pair<string, string> pss;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<pii> vii;
typedef vector<ll> vl;
typedef vector<vl> vvl;
bool visa[(int)1e6];
#include "dreaming.h"
const int Ne = 1e5 + 5;
int mx, idmx;
int mxres;
bool th = false;
vii x[Ne];
vii res;
int R;
int mn = 1e9, idmn = 1e9;
int dfs(int idx, int cst, int prnt) {
int res = 0;
visa[idx] = true;
if (idx == R && th) {
return cst;
}
for (auto i : x[idx]) {
if (i.first == prnt) continue;
res += dfs(i.first, cst + i.second, idx);
}
if (res > 0) {
int mex = max(cst, mx - cst);
if (mex < mn) {
mn = mex;
idmn = idx;
}
return cst;
}
if (mx < cst) {
mx = cst;
idmx = idx;
}
if (cst == 0 && !th) return idmx;
if (th) {
return 0;
}
return 0;
}
int travelTime(int N, int M, int L, int A[], int B[], int T[]) {
for (int i = 0; i < M; i++) {
x[A[i]].push_back({ B[i],T[i] });
x[B[i]].push_back({ A[i],T[i] });
}
for (int i = 0; i < N; i++) {
if (visa[i]) continue;
th = false;
mx = 0; idmx = 0;
int a = dfs(i, 0, -1);
mx = 0; idmx = 0;
int b = dfs(a, 0, -1);
mxres = max(mxres, mx);
if (x[i].empty()) {
res.push_back({ 0,i });
continue;
}
th = true;
R = b;
mn = 1e9, idmn = 1e9;
dfs(a, 0, -1);
res.push_back({ mn,idmn });
}
sort(res.begin(), res.end());
for (int i = 0; i < res.size() - 1; i++) {
x[res[i].second].push_back({ res[res.size() - 1].second,L });
//cout << res[i].second << " ";
}
mx = 0;
for (int i = res.size() - 1; i >= res.size() - 2 && i >= 0; i--, mx += L) {
mx += res[i].first;
}
mx -= L;
mxres = max(mxres,mx);
if (res.size() > 2) {
mxres = max(mxres,L*2+res[res.size()-2].first+res[res.size()-3].first);
}
return max(mxres, mx);
}
