#include <bits/stdc++.h>
#include "dreaming.h"
using namespace std;
using ll = long long;
vector<pair<int, ll>> adj[100100];
bool vis[100100];
int big[100100];
ll dp[100100][2], mn, mx = 0;
void dfs(int v, int p = -1) {
vis[v] = 1;
for (auto& [x, w] : adj[v]) {
if (x == p) continue;
dfs(x, v);
dp[v][1] = max(dp[v][1], dp[x][0] + w);
if (dp[v][1] > dp[v][0]) swap(dp[v][0], dp[v][1]), big[v] = x;
}
}
void dfs2(int v, int p = -1, ll prev = 0) {
dp[v][1] = max(dp[v][1], prev);
if (dp[v][1] > dp[v][0]) swap(dp[v][0], dp[v][1]);
mn = min(mn, dp[v][0]);
mx = max(mx, dp[v][0] + dp[v][1]);
for (auto& [x, w] : adj[v]) {
if (x == p) continue;
if (x == big[v]) dfs2(x, v, max(prev, dp[v][1]) + w);
else dfs2(x, v, max(prev, dp[v][0]) + w);
}
}
int travelTime(int n, int m, int L, int a[], int b[], int c[]) {
memset(big, -1, sizeof big);
for (int i = 0;i < m;i++) {
adj[a[i]].push_back({ b[i],c[i] });
adj[b[i]].push_back({ a[i],c[i] });
}
vector<ll> ans;
for (int i = 0;i < n;i++) {
if (vis[i]) continue;
mn = 1e18;
dfs(i);
dfs2(i);
ans.push_back(mn);
}
sort(ans.begin(), ans.end(), greater<ll>());
if (ans.size() == 1) {
return mx;
}
if (ans.size() == 2) {
return max(mx, ans[0] + ans[1] + L);
}
return max({ mx,ans[0] + ans[1] + L, ans[1] + ans[2] + 2 * L });
}
// int U[19], V[19], W[19];
// int main() {
// int n, m, l;
// cin >> n >> m >> l;
// for (int i = 0;i < m;i++) {
// cin >> U[i] >> V[i] >> W[i];
// }
// cout << travelTime(n, m, l, U, V, W);
// }
/*
12 8 2
0 8 4
8 2 2
2 7 4
5 11 3
5 1 7
1 3 1
1 9 5
10 6 3
*/
