#include <bits/stdc++.h>
#include "dreaming.h"
using namespace std;
using ll = long long;
using P = pair<int, int>;
#define all(x) x.begin(), x.end()
#define rep(i, l, n) for (int i = l; i < (n); ++i)
#define sz(x) (int)x.size()
const char nl = '\n';
const int mod = 1e9+7;
const int N = 1e3+10;
int vis[N], mx, s;
P from[N]; vector<P> g[N];
void dfs(int nd, int dis, int p) {
if (dis > mx)mx = dis, s = nd;
for (auto [i, w]: g[nd])
if (i != p)dfs(i, dis+w, nd);
}
void yol(int nd, int p, int dis) {
from[nd] = {p, dis};
for (auto [i, w]: g[nd])
if (i != p)yol(i, nd, dis+w);
}
P calc(int nd) {
mx = s = 0;
dfs(nd, 0, nd);
int a = s;
mx = s = 0;
dfs(a, 0, a);
int b = s;
yol(a, -1, 0);
int c1, c2 = -1;
while (from[b].first != -1) {
if (from[b].second >= mx/2)c1 = b;
else if (c2 == -1)c2 = b;
b = from[b].first;
}
return {c1, c2};
}
int travelTime(int n, int m, int l, int aa[], int ba[], int tt[]) {
rep(i, 0, m) {
//int a, b, t; cin >> a >> b >> t;
g[aa[i]].push_back(P(ba[i], tt[i]));
g[ba[i]].push_back(P(aa[i], tt[i]));
}
int a = 1, b = 2;
if (n != 2) {
rep(i, 0, n)
if (sz(g[i]) == 0)b = i;
rep(i, 0, n)
if (sz(g[i]))a = i;
}
//cout << a << " " << b << nl;
P x = calc(a);
g[x.first].push_back({b, l});
g[b].push_back({x.first, l});
calc(x.first);
int res = mx;
g[x.first].pop_back();
g[b].pop_back();
g[x.second].push_back({b, l});
g[b].push_back({x.second, l});
calc(x.second);
res = min(res, mx);
return res;
}
//int32_t main() {
//ios_base::sync_with_stdio(0);
//cin.tie(0);
//solve();
//return 0;
//}
