#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define all(x) begin(x), end(x)
#define sz(x) (int)x.size()
#define pb push_back
#include "dreaming.h";
const int maxn = 100001;
vector<pair<int, int>> adj[maxn];
bool vis[maxn];
int d[maxn];
pair<int, int> par[maxn];
vector<int> v;
void dfs(int s, int p, int w){
par[s] = {p, w};
d[s] = d[p] + w;
vis[s] = true;
v.pb(s);
for(auto [u, ww]: adj[s]){
if(u == p) continue;
dfs(u, s, ww);
}
}
int travelTime(int N, int M, int L, int A[], int B[], int T[]){
for(int i=0; i<M; i++){
int a = A[i], b = B[i], c = T[i];
a++; b++;
adj[a].pb({b, c}); adj[b].pb({a, c});
}
vector<vector<int>> vec;
for(int i=1; i<=N; i++){
if(!vis[i]){
dfs(i, 0, 0);
int mx = 0;
for(auto j: v){
mx = max(mx, d[j]);
}
int a = 0;
for(auto j: v){
if(d[j] == mx){
a = j;
break;
}
}
v.clear();
dfs(a, 0, 0);
mx = 0;
for(auto j: v){
mx = max(mx, d[j]);
}
int b = 0;
for(auto j: v){
if(d[j] == mx){
b = j;
break;
}
}
v.clear();
vector<int> v1;
int c = b;
while(c != a){
int w = par[c].second;
v1.pb(w);
c = par[c].first;
}
if(sz(v1) == 0){
vec.pb({0, 0, 0});
}
else{
int x = 0, y = 0;
for(auto w: v1) y += w;
for(auto w: v1){
if(x <= y and x+w >= y-w){
vec.pb({x, w, y-w});
break;
}
x += w;
y -= w;
}
}
}
}
sort(all(vec), [](vector<int> x, vector<int> y){
return x[0] + x[1] + x[2] >= y[0] + y[1] + y[2];
});
auto f = [&](vector<int> v1, vector<int> v2){
int x1 = v1[0], w1 = v1[1], y1 = v1[2];
int x2 = v2[0], w2 = v2[1], y2 = v2[2];
int a = min(x1+w1, y1+w1);
int b = min(x2+w2, y2+w2);
int d1 = x1 + w1 + y1;
int d2 = x2 + w2 + y2;
int d3 = a + b + L;
if(d1 == max({d1, d2, d3})) return v1;
if(d2 == max({d1, d2, d3})) return v2;
if(a <= b){
if(a+L >= b) return vector<int>({a, L, b});
else return vector<int>({a+L, w2, b-w2});
}
else{
if(b+L >= a) return vector<int>({b, L, a});
else return vector<int>({b+L, w1, a-w1});
}
};
vector<int> ans = vec[0];
for(int i=1; i<sz(vec); i++){
ans = f(ans, vec[i]);
}
return ans[0] + ans[1] + ans[2];
}
