#include <bits/stdc++.h>
#include "dreaming.h"
#define pii pair<int,int>
#define pli pair<long long,pii>
#define fi first
#define se second
#define vi vector<int>
#define vii vector<pii>
#define all(x) x.begin(),x.end()
using namespace std;
typedef long long ll;
typedef long double ld;
const int inf = 1e9;
const ll linf = 1e16;
const double pi = acos(-1);
const int maxN = 1e5 + 5;
vector<pii> a[maxN];
int down[maxN];
int up[maxN];
int ans = 0;
void dfsDown(int u,int p){
down[u] = 0;
for (int i = 0; i < a[u].size(); i++){
int v,w;
tie(v,w) = a[u][i];
if (v == p) continue;
dfsDown(v,u);
down[u] = max(down[u], down[v] + w);
}
}
void dfsUp(int u,int p,int& res){
res = min(res, max(down[u], up[u]));
ans = max(ans, down[u] + up[u]);
int m1 = -1,m2 = -1;
int i1 = -1,i2 = -1;
for (int i = 0; i < a[u].size(); i++){
int v = a[u][i].fi;
int w = a[u][i].se;
if (v == p) continue;
if (down[v] + w > m2){
m2 = down[v] + w;
i2 = v;
}
if (m2 > m1){
swap(m2,m1);
swap(i2,i1);
}
}
for (int i = 0; i < a[u].size(); i++){
int v = a[u][i].fi;
int w = a[u][i].se;
if (v == p) continue;
if (i1 == v && i2 == -1){
up[v] = up[u] + w;
}
else{
up[v] = max(up[u] + w,(v == i1 ? m2 : m1) + w);
}
dfsUp(v,u,res);
}
}
int getVal(int u){
dfsDown(u,-1);
int res = inf;
dfsUp(u,-1,res);
return res;
}
int travelTime(int N,int M,int L,int A[],int B[],int T[]){
for (int i = 0; i < M; i++){
int u = A[i] + 1;
int v = B[i] + 1;
int w = T[i];
a[u].push_back(pii(v,w));
a[v].push_back(pii(u,w));
}
vector<int> v;
memset(down,-1,sizeof(down));
for (int i = 1; i <= N; i++){
if (down[i] != -1) continue;
v.push_back(getVal(i));
}
sort(all(v),greater<int>());
if (v.size() == 2) ans = max(ans, v[0] + v[1] + L);
if (v.size() >= 3) ans = max(ans, max(v[0] + v[1] + L, v[1] + v[2] + L + L));
return ans;
}
