#include "dreaming.h"
#include <bits/stdc++.h>
using namespace std;
const int N = 100'000;
vector<pair<int,int>> adj[N];
bool visited[N];
void dfs_cc(int s, int e, vector<int> &g){
g.push_back(s);
visited[s] = true;
for (auto [u,w]: adj[s]){
if (u == e) continue;
dfs_cc(u, s, g);
}
}
int travelTime(int n, int m, int L, int A[], int B[], int T[]) {
for (int i=0;i<N;i++) visited[i] = false;
for (int i=0;i<m;i++){
int u = A[i], v = B[i], w = T[i];
adj[u].push_back({v, w});
adj[v].push_back({u, w});
}
vector<vector<int>> subG;
for (int i=0;i<n;i++) {
if (!visited[i]){
vector<int> cur;
dfs_cc(i, -1, cur);
subG.push_back(cur);
}
}
int ans=0;
for (auto G: subG){
int s = -1, e = -1;
for (auto x: G){
if (adj[x].size() == 1){
if (s == -1) s=x;
else e=x;
}
}
int par=s;
int i = s, j = e;
int sum = adj[i][0].second;
i = adj[i][0].first;
while (i != j){
for (auto [u,w]: adj[i]){
if (u == par) continue;
else {
par = i;
i = u;
sum += w;
}
}
}
i = s, j = e;
i = adj[i][0].first;
int ss=0;
int cur=sum;
while (i != j){
for (auto [u,w]: adj[i]){
if (u == par) continue;
else {
par = i;
i = u;
ss += w;
cur = min(cur, max(ss, sum-ss));
}
}
}
ans += cur;
}
return ans + L;;
}
