#include <bits/stdc++.h>
#include "dreaming.h"
using namespace std;
#define pii pair<int, int>
#define f first
#define s second
const int mx = 1e5 + 5;
vector<pii> adj[mx]; pii in[mx]; bool vis[mx]; int lg;
void dfs1(int i, int p){
vis[i] = 1;
for (auto [x, w] : adj[i]) if (x != p){
dfs1(x, i); int tmp = in[x].f + w;
if (tmp > in[i].f) in[i].s = in[i].f, in[i].f = tmp;
else if (tmp > in[i].s) in[i].s = tmp;
}
}
void dfs2(int i, int p, int pout, int &mnD){
mnD = min(mnD, max(pout, in[i].f)); lg = max(lg, in[i].f + pout);
for (auto [x, w] : adj[i]) if (x != p){
int sib = (in[i].f == in[x].f + w) ? in[i].s : in[i].f;
int out = max(sib, pout) + w;
dfs2(x, i, out, mnD);
}
}
int travelTime(int n, int m, int l, int A[], int B[], int T[]){
for (int i = 0; i < m; i++){
adj[A[i]].push_back({B[i], T[i]});
adj[B[i]].push_back({A[i], T[i]});
}
int w[3] = {-l, -l, -l};
for (int i = 0; i < n; i++) if (!vis[i]){
int mnD = 1e9; dfs1(i, 0); dfs2(i, 0, 0, mnD);
if (mnD > w[0]) w[2] = w[1], w[1] = w[0], w[0] = mnD;
else if (mnD > w[1]) w[2] = w[1], w[1] = mnD;
else if (mnD > w[2]) w[2] = mnD;
}
return max({w[0] + w[1] + l, w[1] + w[2] + 2 * l, lg});
}
