#include <bits/stdc++.h>
using namespace std;
#include "dreaming.h"
int travelTime(int n,int m,int q,int A[],int B[],int C[]){
vector<vector<pair<int,int>>> G(n);
for (int i(0);i < m;++i) G[A[i]].emplace_back(B[i],C[i]),G[B[i]].emplace_back(A[i],C[i]);
vector<int> vis(n,1),mos(n);
auto dfs = [&](auto& dfs,int x,int p,int d = 0) -> pair<int,int> {
pair<int,int> ret(0,x);
for (auto [y,z]:G[x]) if (y!=p) ret = max(ret,dfs(dfs,y,x,z));
ret.first += d;
if (vis[x]) vis[x] = 0,mos[x] = ret.first;
return ret;
};
auto dp = [&](auto& dp,int x,int p,int w = 0) -> int {
multiset<int> S; S.emplace(w);
for (auto [y,z]:G[x]) if (y!=p) S.emplace(mos[y]);
int t = *S.rbegin(),ret = t;
for (auto [y,z]:G[x]) if (y!=p) ret = min(ret,dp(dp,y,x,(t==mos[y]?*next(S.rbegin()):t)+z));
return ret;
};
int res(0);
vector<int> S;
for (int i(0);i < n;++i) if (vis[i]){
res = max(res,dfs(dfs,dfs(dfs,i,-1).second,-1).first);
S.emplace_back(dp(dp,i,-1));
}
sort(S.begin(),S.end(),greater<int>());
if (S.size()>1) res = max(res,S[0]+S[1]+q);
if (S.size()>2) res = max(res,S[1]+S[2]+2*q);
return res;
}
