#include "dreaming.h"
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define dbg(x) cerr << #x << ": " << x << '\n';
vector<vector<pair<int, int>>> arr;
vector<bool> vis;
void dfs(int node, int prev, int w, ll &sum){
vis[node] = 1;
sum += w;
for(pair<int, int> i : arr[node]){
if(i.first == prev) continue;
dfs(i.first, node, i.second, sum);
}
}
void dfs2(int node, int prev, int w, ll sum, ll prevsum, ll &maxn){
ll s2 = prevsum + w;
ll s1 = sum - s2;
ll ma = max(s1, s2);
maxn = min(ma, maxn);
for(pair<int, int> &i : arr[node]){
if(i.first == prev) continue;
dfs2(i.first, node, i.second, sum, s2, maxn);
}
}
int travelTime(int N, int M, int L, int A[], int B[], int T[]) {
arr.assign(N, vector<pair<int, int>>());
vis.assign(N, 0);
for(int i = 0; i < M; i++){
arr[A[i]].push_back({B[i], T[i]});
arr[B[i]].push_back({A[i], T[i]});
}
vector<int> heads;
for(int i = 0; i < arr.size(); i++){
if(arr[i].size() == 1){
heads.push_back(i);
}
}
bool t = true;
ll max1 = LLONG_MAX, max2 = LLONG_MAX, sum1 = 0, sum2 = 0;
for(int &i : heads){
if(vis[i]) continue;
if(t){
dfs(i, i, 0, sum1);
t = 0;
dfs2(i, i, 0, sum1, 0, max1);
} else {
dfs(i, i, 0, sum2);
dfs2(i, i, 0, sum2, 0, max2);
}
}
return max1 + max2 + L;
}
