#include "dreaming.h"
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 100005;
vector<pair<int, int>> adj[MAXN], cdist[MAXN];
bool pro[MAXN];
int dia, mxd;
int dfs(int x, int par){
pro[x] = 1;
for (auto nxt : adj[x]){
int nn, nd; tie(nn, nd) = nxt;
if (nn == par) continue;
cdist[x].push_back({nd + dfs(nn, x), nn});
}
for (int i = 0; i < 2; i++) cdist[x].push_back({0, -1});
sort(cdist[x].begin(), cdist[x].end(), greater<pair<int, int>>());
return cdist[x][0].first;
}
void dfs2(int x, int par, int pd){
dia = max(dia, max(pd + cdist[x][0].first, cdist[x][0].first + cdist[x][1].first));
mxd = min(mxd, max(pd, cdist[x][0].first));
for (auto nxt : adj[x]){
int nn, nd; tie(nn, nd) = nxt;
if (nn == par) continue;
if (nn == cdist[x][0].second) dfs2(nn, x, max(pd, cdist[x][1].first) + nd);
else dfs2(nn, x, max(pd, cdist[x][0].first) + nd);
}
}
int travelTime(int nodes, int edges, int L, int A[], int B[], int T[]) {
for (int i = 0; i < edges; i++){
int a = A[i], b = B[i], c = T[i];
adj[a].push_back({b, c});
adj[b].push_back({a, c});
}
int ans = 0; vector<int> mxdvec;
for (int i = 0; i < nodes; i++)
if (!pro[i]){
dia = 0, mxd = 2e9;
dfs(i, -1); dfs2(i, -1, 0);
ans = max(ans, dia);
mxdvec.push_back(mxd);
}
sort(mxdvec.begin(), mxdvec.end(), greater<int>());
if (mxdvec.size() >= 2) ans = max(ans, mxdvec[0] + mxdvec[1] + L);
if (mxdvec.size() >= 3) ans = max(ans, mxdvec[1] + mxdvec[2] + 2 * L);
return ans;
}
