#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<int>());
ll l = mx, r = 1e10;
while (l < r) {
ll mid = (l + r) / 2;
ll nowmx = ans[0], tmx = 0;
ll cnt = 0;
bool ch = 1;
for (int i = 1;i < (int)ans.size();i++) {
cnt++;
if (cnt * L + nowmx + ans[i] > mid) {
cnt = 1;
nowmx = max(nowmx, tmx);
if (cnt * L + nowmx + ans[i] > mid) {
ch = 0;
break;
}
}
tmx = max(tmx, ans[i] + cnt * L);
}
if (ch) r = mid;
else l = mid + 1;
}
return 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
*/
