#include "bits/stdc++.h"
#include <ext/pb_ds/assoc_container.hpp>
#include "dreaming.h"
using namespace __gnu_pbds;
typedef long long ll;
#define F first
#define S second
#define PB push_back
#define MP make_pair
#define all(c) (c).begin(), (c).end()
#define pii pair<int,int>
#define pll pair<long long, long long>
#define sz(a) (int)a.size()
// permutation of the last layer
#define LOO(i,a,b) for (int i = a; i <= b; i++)
#define OOL(i,a,b) for (int i = b; i >= a; i--)
#define max3(a, b, c) max(max(a, b), c)
#define min3(a, b, c) min(min(a, b), c)
using namespace std;
vector<vector<pii>> graph;
vector<bool> visited;
ll best = 1e12;
vector<ll> costs;
ll dfs1(int index, int par) {
ll worsty = 0;
for (pii xs: graph[index]) {
int child = xs.F;
int cost = xs.S;
if (child==par) continue;
worsty = max(worsty, dfs1(child, index)+cost);
}
costs[index] = worsty;
visited[index] = true;
return worsty;
}
ll dfs2(int index, int par, ll worst) {
ll worsty1 = 0;
int index1 = -1;
ll worsty2 = 0;
for (pii xs: graph[index]) {
int child = xs.F;
int cost = xs.S;
if (child==par) continue;
ll final = cost+costs[child];
if (final>=worsty1) {
worsty2 = max(worsty2, worsty1);
worsty1 = final;
index1 = child;
}
else if (final>=worsty2) {
worsty2 = final;
}
}
if (max(worsty1, worst) < best) {
best = max(worsty1, worst);
}
for (pii xs: graph[index]) {
int child = xs.F;
ll cost = xs.S;
if (child==par) continue;
if (child==index1) {
dfs2(child, index, max(worsty2+cost, worst + cost));
}
else {
dfs2(child, index, max(worsty1+cost, worst + cost));
}
}
visited[index] = true;
return max(worsty1, worst);
}
int travelTime(int N,int M,int L, int A[],int B[],int T[]) {
graph.resize(N);
LOO(i, 0, M-1) {
graph[A[i]].PB(MP(B[i], T[i]));
graph[B[i]].PB(MP(A[i], T[i]));
}
visited = vector(N, false);
costs.resize(N);
LOO(i, 0, N-1) {
if (visited[i]) continue;
dfs1(i, i);
}
visited = vector(N, false);
vector<ll> unreal;
LOO(i, 0, N-1) {
if (visited[i]) continue;
best = 1e12;
dfs2(i, i, 0);
unreal.PB(best);
}
sort(all(unreal));
reverse(all(unreal));
ll best = unreal[0];
LOO(i, 1, sz(unreal)-1) {
best = max(best, unreal[0]+unreal[i]+L*i);
}
return best;
}
