#include "dreaming.h"
#include <bits/stdc++.h>
using namespace std;
typedef pair<int, int> pii;
const int MAXN = 1e2 + 10;
const int INF = 2e9 + 10;
vector<pii> adj[MAXN];
bool mrk[MAXN];
int dist[MAXN][MAXN];
int max_dist[MAXN];
int n, resp;
void dfs(int s, int v) {
mrk[v] = true;
for (auto [w, c]: adj[v]) {
if (mrk[w]) continue;
dist[s][w] = dist[s][v] + c;
dfs(s, w);
}
}
void build_dist(int v) {
for (int i = 0; i < n; i++) {
dist[v][i] = -INF;
mrk[i] = false;
}
dist[v][v] = 0;
dfs(v, v);
max_dist[v] = 0;
for (int i = 0; i < n; i++) {
max_dist[v] = max(max_dist[v], dist[v][i]);
}
resp = max(resp, max_dist[v]);
}
int travelTime(int N, int M, int L, int A[], int B[], int T[]) {
// subtask 3
// assert(M == N - 2);
n = N;
resp = 2e9 + 10;
for (int i = 0; i < n; i++) {
adj[i].clear();
}
for (int i = 0; i < M; i++) {
adj[A[i]].push_back({B[i], T[i]});
adj[B[i]].push_back({A[i], T[i]});
}
for (int i = 0; i < n; i++) {
build_dist(i);
}
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
if (dist[i][j] != -INF) continue;
resp = min(resp, max_dist[i] + max_dist[j] + L);
}
}
return resp;
}
