#include <bits/stdc++.h>
using namespace std;
#include "dreaming.h"
int travelTime(int n,int m,int q,int EA[],int EB[],int ET[]){
vector<vector<pair<int,int>>> G(n); for (int i(0);i < m;++i){
G[EA[i]].emplace_back(EB[i],ET[i]),G[EB[i]].emplace_back(EA[i],ET[i]);
}
vector<int> dist0(n),dist1(n),A,vis(n,1);
auto dfs0 = [&](auto& dfs,int x,int p,int d) -> pair<int,int> {
pair<int,int> ret(d,x);
A.emplace_back(x),vis[x] = 0;
for (auto [y,z]:G[x]) if (y!=p) ret = max(ret,dfs(dfs,y,x,d+z));
return ret;
};
auto dfs1 = [&](auto& dfs,int x,int p,int d,vector<int>& dist) -> pair<int,int> {
pair<int,int> ret(d,x); dist[x] = d;
for (auto [y,z]:G[x]) if (y!=p) ret = max(ret,dfs(dfs,y,x,d+z,dist));
return ret;
};
vector<int> R;
for (int i(0);i < n;++i) if (vis[i]){
int x = dfs0(dfs0,i,-1,0).second,y = dfs1(dfs1,x,-1,0,dist0).second;
dfs1(dfs1,y,-1,0,dist1);
R.emplace_back(1e9);
for (int k:A) R.back() = min(R.back(),max(dist0[k],dist1[k]));
A.clear();
}
sort(R.begin(),R.end(),greater<int>());
return R[0]+(R.size()==1?0:R[1]+q);
}
