#include "dreaming.h"
#include <bits/stdc++.h>
//#include <ext/pb_ds/assoc_container.hpp>
//#include <ext/pb_ds/tree_policy.hpp>
#define all(v) v.begin(), v.end()
#define pb push_back
#define ss second
#define ff first
#define vt vector
using namespace std;
//using namespace __gnu_pbds;
typedef long long ll;
typedef vector<int> vi;
typedef vector<ll> vll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef pair<double, int> pdi;
const ll inf = 1e18 + 10000;
const int mod = 1e9+7;
const int maxn = 2e6 + 12;
vt<pii> g[maxn];
ll mx[maxn][2], ret, rad;
bool was[maxn];
void dfs(int v){
was[v] = 1;
for(auto i : g[v]){
if(!was[i.ff]){
dfs(i.ff);
int x = mx[i.ff][0] + i.ss;
if(mx[v][0] < x)mx[v][1] = mx[v][0], mx[v][0] = x;
else if(mx[v][1] < x)mx[v][1] = x;
}
}
}
void rlx(int v, ll x, int pr){
for(auto i : g[v]){
if(i.ff != pr){
if(mx[v][0] == i.ss + mx[i.ff][0])rlx(i.ff, max(x, mx[v][1]) + i.ss, v);
else rlx(i.ff, max(x, mx[v][0]) + i.ss, v);
}
}
if(x > mx[v][0])mx[v][1] = mx[v][0], mx[v][0] = x;
else if(x > mx[v][1])mx[v][1] = x;
ret = max(ret, mx[v][0] + mx[v][1]);
rad = min(rad, mx[v][0]);
}
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]});
}
vt<ll> sr;
for(int i = 0; i < n; i++){
if(!was[i]){
dfs(i);
rad = mx[i][0];
rlx(i, 0, 0);
sr.pb(rad);
}
}
sort(all(sr));
if(sr.size() > 1)ret = max(ret, l + sr.back() + sr[sr.size() - 2]);
return ret;
}
