#include "dreaming.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef tuple<ll, ll, ll> plll;
typedef vector<plll> vplll;
typedef pair<ll, ll> pll;
typedef vector<ll> vll;
typedef vector<pll> vpll;
typedef vector<vector<pll>> vvpll;
typedef vector<vector<ll>> vvll;
typedef vector<bool> vb;
typedef vector<vector<bool>> vvb;
#define loop(i, s, e) for (ll i = (s); i < (e); ++i)
#define loopr(i, e, s) for (ll i = (e)-1; i >= (s); --i)
#define all(a) a.begin(), a.end()
const ll inf = 1e9 + 7;
ll mx_dis = 0;
ll nd = 0;
vb vis;
ll in = 0;
vector<multiset<pll>> g;
void dfs(ll node, ll dis) {
vis[node]=1;
in++;
if (dis>mx_dis) {
mx_dis = dis;
nd = node;
}
for (auto [it, d] : g[node]) {
if (!vis[it]) dfs(it,dis+d);
}
}
void dfs1(ll node ,ll dis) {
vis[node]=1;
if (dis>mx_dis) {
mx_dis = dis;
nd = node;
}
for (auto [it, d] : g[node]) {
if (!vis[it]) {
dfs1(it,dis+d);
}
}
}
int travelTime(int n, int m, int l, int A[], int B[], int T[]) {
g.resize(n);
vis.resize(n ,false);
loop(i,0,m) {
g[A[i]].insert({B[i], T[i]});
g[B[i]].insert({A[i], T[i]});
}
ll ans = inf;
loop(i,0,n) {
loop(j,i+1, n) {
g[i].insert({j,l});
g[j].insert({i, l});
in = 0;
vis.assign(n, false);
mx_dis = 0;
dfs(0,0);
if (in!=n) continue;
vis.assign(n, false);
mx_dis = 0;
dfs1(nd, 0);
ans = min(ans, mx_dis);
g[i].erase(g[i].find({j,l}));
g[j].erase(g[j].find({i, l}));
}
}
return ans;
}
