#include "dreaming.h"
#include <bits/stdc++.h>
#pragma GCC optimize ("O2,unroll-loops")
//#pragma GCC optimize("no-stack-protector,fast-math")
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<pii, int> piii;
typedef pair<ll, ll> pll;
#define debug(x) cerr<<#x<<'='<<(x)<<endl;
#define debugp(x) cerr<<#x<<"= {"<<(x.first)<<", "<<(x.second)<<"}"<<endl;
#define debug2(x, y) cerr<<"{"<<#x<<", "<<#y<<"} = {"<<(x)<<", "<<(y)<<"}"<<endl;
#define debugv(v) {cerr<<#v<<" : ";for (auto x:v) cerr<<x<<' ';cerr<<endl;}
#define all(x) x.begin(), x.end()
#define pb push_back
#define kill(x) return cout<<x<<'\n', 0;
const int inf=1000000010;
const ll INF=1000000000000001000LL;
const int mod=1000000007;
const int MAXN=100010, LOG=20;
int n, m, k, u, v, x, y, t, a, b, ans;
int D[2][MAXN], mark[MAXN];
vector<pii> G[MAXN];
vector<int> vec, V;
void dfs(int node, int *dist){
if (!mark[node]) V.pb(node);
mark[node]++;
for (pii p:G[node]) if (mark[p.first]<mark[node]){
dist[p.first]=dist[node]+p.second;
dfs(p.first, dist);
}
}
int travelTime(int n, int m, int L, int A[], int B[], int T[]){
for (int i=0; i<m; i++){
G[A[i]].pb({B[i], T[i]});
G[B[i]].pb({A[i], T[i]});
}
for (int i=0; i<n; i++) if (!mark[i]){
dfs(i, D[0]);
int v=i;
for (int u:V) if (D[0][u]>D[0][v]) v=u;
dfs(v, D[1]);
for (int u:V) if (D[1][u]>D[1][v]) v=u;
D[0][v]=0;
dfs(v, D[0]);
int res=inf;
for (int u:V){
int val=max(D[0][u], D[1][u]);
ans=max(ans, val);
res=min(res, val);
}
vec.pb(res);
V.clear();
}
// debugv(vec)
// debug(ans)
if (vec.size()==1) return ans;
if (vec.size()==2) return max(ans, vec[0]+vec[1]+L);
sort(all(vec));
reverse(all(vec));
vec.resize(3);
int res=inf;
do{
int a=vec[0], x=vec[1], y=vec[2];
res=min(res, max(2*L+x+y, L+x+a));
} while(next_permutation(all(vec)));
return max(ans, res);
}
