#include<bits/stdc++.h>
#include "dreaming.h"
using namespace std;
#define ll long long
#define fi first
#define se second
#define pb push_back
#define ALL(n) n.begin(), n.end()
#define mask(n) (1ll << (n))
#define ck(n, k) (((n) >> (k))&1)
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
void dfs1(int u, vector<vector<pair<int,int>>>& adj, vector<bool>& vis, vector<int>& dp1, vector<int>& dp2) {
vis[u] = true;
for (auto e: adj[u]) {
if (vis[e.fi]) continue;
int v = e.fi, t = e.se;
dfs1(v, adj, vis, dp1, dp2);
if (dp1[v] + t > dp1[u]) {
dp2[u] = dp1[u];
dp1[u] = dp1[v] + t;
} else dp2[u] = max(dp2[u], dp1[v] + t);
}
}
int dfs2(int u, int pa, int pathTo, vector<vector<pair<int,int>>>& adj, vector<int>& dp1, vector<int>& dp2, int& ans) {
int res = max(pathTo, dp1[u]);
ans = max(ans, res);
for (auto e : adj[u]) {
if (e.fi == pa) continue;
int v = e.fi, t = e.se;
if (dp1[u] == dp1[v] + t) res = min(res, dfs2(v, u, max(dp2[u], pathTo) + t, adj, dp1, dp2, ans));
else res = min(res, dfs2(v, u, max(dp1[u], pathTo) + t, adj, dp1, dp2, ans));
}
return res;
}
int travelTime(int N, int M, int L, int A[], int B[], int T[]) {
vector<vector<pair<int,int>>> adj(N);
vector<bool> vis(N, false);
vector<int> dp1(N, 0);
vector<int> dp2(N, 0);
for (int i = 0; i < M ;i++) {
adj[A[i]].pb({B[i], T[i]});
adj[B[i]].pb({A[i], T[i]});
}
int ans = 0, ans1 = -1, ans2 = -1;
for (int i = 0; i < N; i++)
if (!vis[i]) {
dfs1(i, adj, vis, dp1, dp2);
int cur = dfs2(i, -1, 0, adj, dp1, dp2, ans);
if (cur > ans1) {
ans2 = ans1;
ans1 = cur;
} else {
ans2 = max(ans2, cur);
}
}
if (ans1 != -1 && ans2 != -1) ans = max(ans, ans1 + ans2 + L);
return ans;
}
// int main()
// {
// ios_base::sync_with_stdio(0);
// cin.tie(0); cout.tie(0);
// int testcase = 1;
// // cin >> testcase;
// int n, m, l;
// cin >> n >> m >> l;
// int a[m], b[m], t[m];
// for (int i = 0; i < m; i++) {
// cin >> a[i] >> b[i] >> t[i];
// }
// cout << travelTime(n, m, l, a, b, t);
// return 0;
// }
