#include "dreaming.h"
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define ff first
#define ss second
#define pb push_back
#define mk make_pair
#define IOS ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define MOD 1000000007
#define MOD1 1000000009
#define sqr(x) sqr((x)*(x))
void debug_out() { cerr << endl; }
template<typename Head, typename... Tail> void debug_out(Head H, Tail... T) { cerr << ' ' << H; debug_out(T...); }
#ifdef BE_DEBUG
#define debug(...) cerr << "\033[1;31m(" << #__VA_ARGS__ << "):\033[0m", debug_out(__VA_ARGS__)
#else
#define debug(...)
#endif
const int BB = 100005;
vector<pair<int,int> > edge[BB];
bool visited[BB];
int mx, num_of_node;
int a[BB],b[BB],ans;
vector<int> v,gold;
void dfs(int node, int dis, int type) {
visited[node] = 1;
if(type == 0) v.pb(node);
if(dis > mx) {
mx = dis;
num_of_node = node;
}
if(type >= 1) a[node] = max(dis,a[node]);
for(auto x: edge[node]) {
if(visited[x.ff] == 1) continue;
dfs(x.ff, dis + x.ss, type);
}
}
int travelTime(int N, int M, int L, int A[], int B[], int T[]) {
for(int i = 0 ; i < M; i ++) {
edge[A[i]].pb({B[i], T[i]});
edge[B[i]].pb({A[i], T[i]});
}
for(int i = 0; i < N; i ++) {
if(visited[i] == 1) continue;
mx = -1;
v.clear();
dfs(i,0,0);
for(auto x: v) visited[x] = 0;
mx = -1;
dfs(num_of_node,0,1);
for(auto x: v) visited[x] = 0;
dfs(num_of_node,0,2);
ans = max(ans,mx);
int mn = 1e9;
for(auto x: v) {
mn = min(mn,a[x]);
}
gold.pb(mn);
}
sort(gold.begin(), gold.end());
reverse(gold.begin(), gold.end());
if(gold.size() == 1) {
return max(ans, gold[0]);
}
if(gold.size() == 2) {
return max(ans, gold[0] + gold[1] + L);
}
return max(ans, max(gold[0] + gold[1] + L, gold[1] + gold[2] + L + L));
}
