#include "dreaming.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef tuple<ll, ll, ll> plll;
typedef vector<plll> vplll;
typedef pair<ll, ll> pll;
typedef vector<ll> vll;
typedef vector<pll> vpll;
typedef vector<vector<pll>> vvpll;
typedef vector<vector<ll>> vvll;
typedef vector<bool> vb;
const ll inf = 1e9 + 7;
vvpll g;
ll sum1 = 0, sum2 = 0;
ll max_to_node_1 = inf, max_to_node_2 = inf;
vb vis;
void dfs_1(ll node, ll) {
stack<ll> st;
st.push(node);
vis[node] = true;
while (!st.empty()) {
ll u = st.top(); st.pop();
for (auto [v, w] : g[u]) {
if (!vis[v]) {
vis[v] = true;
sum1 += w;
st.push(v);
}
}
}
}
void dfs_2(ll node, ll) {
stack<ll> st;
st.push(node);
vis[node] = true;
while (!st.empty()) {
ll u = st.top(); st.pop();
for (auto [v, w] : g[u]) {
if (!vis[v]) {
vis[v] = true;
sum2 += w;
st.push(v);
}
}
}
}
void calc1(ll node, ll) {
stack<pair<ll,ll>> st;
st.push({node,0});
vis[node] = true;
while (!st.empty()) {
auto [u, d] = st.top(); st.pop();
ll mx = max(d, sum1 - d);
max_to_node_1 = min(max_to_node_1, mx);
for (auto [v, w] : g[u]) {
if (!vis[v]) {
vis[v] = true;
st.push({v, d + w});
}
}
}
}
void calc2(ll node, ll) {
stack<pair<ll,ll>> st;
st.push({node,0});
vis[node] = true;
while (!st.empty()) {
auto [u, d] = st.top(); st.pop();
ll mx = max(d, sum2 - d);
max_to_node_2 = min(max_to_node_2, mx);
for (auto [v, w] : g[u]) {
if (!vis[v]) {
vis[v] = true;
st.push({v, d + w});
}
}
}
}
int travelTime(int n, int m, int l, int A[], int B[], int T[]) {
g.clear();
g.resize(n);
vll deg(n);
for (int i = 0; i < m; ++i) {
g[A[i]].push_back({B[i], T[i]});
g[B[i]].push_back({A[i], T[i]});
deg[A[i]]++; deg[B[i]]++;
}
vis.assign(n, false);
for (int i = 0; i < n; ++i) if (!vis[i]) { dfs_1(i,0); break; }
for (int i = 0; i < n; ++i) if (!vis[i]) { dfs_2(i,0); break; }
vis.assign(n, false);
for (int i = 0; i < n; ++i) if (deg[i] == 1 && !vis[i]) { calc1(i,0); break; }
for (int i = 0; i < n; ++i) if (deg[i] == 1 && !vis[i]) { calc2(i,0); break; }
ll ans = max({sum1, sum2, max_to_node_1 + max_to_node_2 + l});
return ans;
}
