#include "dreaming.h"
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define pb push_back
#define pii pair<int, int>
#define F first
#define S second
const int N = 100005;
int used[N];
int dis[N];
vector <pii> v[N];
void DFS(int node){
used[node] = 1;
dis[node] = 0;
for(pii i : v[node]){
if(!used[i.F]){
used[i.F] = 1;
DFS(i.F);
dis[node] += i.S + dis[i.F];
}
}
}
int getans(int node, int sum){
used[node] = 0;
int res = sum - dis[node];
for(pii i : v[node]){
if(used[i.F]){
res = max(res, dis[i.F] + i.S);
}
}
for(pii i : v[node]){
if(used[i.F]){
used[i.F] = 0;
res = min(res, getans(i.F, sum));
}
}
return res;
}
int travelTime(int n, int m, int l, int a[], int b[], int t[]) {
// return n;
if(n == 1) return 0;
for(int i = 0; i < m; i++){
v[a[i]].pb({b[i], t[i]});
v[b[i]].pb({a[i], t[i]});
}
for(int i = 0; i < n; i++){
if(!used[i]) {
DFS(i);
}
}
vector<int> results;
for(int i = 0; i < n; i++){
if(used[i] != 0){
int cur = getans(i, dis[i]);
results.pb(cur);
// if(results.size() == 1) return cur;
}
}
sort(results.begin(), results.end());
int sz = results.size();
int ans = results[sz - 1];
if(sz >= 2) ans += results[sz - 2] + l;
if(sz >= 3) ans = max(ans, results[sz - 2] + results[sz - 3] + l + l);
return ans;
}
