#include "dreaming.h"
#include<bits/stdc++.h>
#define int long long
using namespace std;
vector<array<int, 2>> ad[100005];
int dis[100005], curmin = 0, curmax = 0;
bool visited[100005];
void dfs(int u)
{
visited[u] = 1; dis[u] = 0;
for(auto &[v, d] : ad[u]) if(visited[v] == 0){
dfs(v); dis[u] = max(dis[u], dis[v] + d);
}
visited[u] = 0;
}
void reroot(int u)
{
visited[u] = 1;
pair<int, int> bestval = {0, 0};
for(auto &[v, d] : ad[u]){
if(bestval.second < dis[v]+d) bestval.second = dis[v]+d;
if(bestval.first < bestval.second) swap(bestval.first, bestval.second);
}
dis[u] = bestval.first;
//cerr<<"A"<<u<<" "<<dis[u]<<endl;
curmin = min(curmin, dis[u]); curmax = max(curmax, bestval.first + bestval.second);
for(auto &[v, d] : ad[u]) if(visited[v] == 0){
int re = dis[u];
if(dis[v] + d == bestval.first) dis[u] = bestval.second;
reroot(v);
dis[u] = re;
}
}
int travelTime(int n, int m, int l, int A[], int B[], int T[]) {
for(int i = 0; i < m; i++){
int u = A[i], v = B[i], d = T[i];
ad[u].push_back({v, d});
ad[v].push_back({u, d});
}
vector<int> a;
for(int i = 0; i < n; i++) if(visited[i] == 0){
curmin = 1e18; dfs(i);
reroot(i);
a.push_back(curmin);
}
sort(a.begin(), a.end(), greater<int>());
int ans = 0;
if(a.size() >= 2) ans = max(ans, a[0] + a[1] + l);
if(a.size() >= 3) ans = max(ans, a[1] + a[2] + 2*l);
return max(ans, curmax);
}
