//In the name of God
#include <bits/stdc++.h>
#include "dreaming.h"
using namespace std;
typedef int ll;
typedef pair<ll, ll> pll;
const ll maxn = 2e5 + 100;
const ll mod = 1e9 + 7;
const ll inf = 1e9;
#define fast_io ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define file_io freopen("input.txt", "r+", stdin);freopen("output.txt", "w+", stdout);
#define pb push_back
#define Mp make_pair
#define F first
#define S second
#define Sz(x) ll((x).size())
#define all(x) (x).begin(), (x).end()
ll d[2][maxn];
vector<pll> g[maxn];
bool vis1[maxn], vis[maxn];
vector<ll> vec;
void dfs1(ll v){
vec.pb(v);
vis1[v] = 1;
for(pll u : g[v]){
if(!vis1[u.F]) dfs1(u.F);
}
return;
}
void dfs(ll v, ll t){
vis[v] = 1;
for(pll u : g[v]){
if(!vis[u.F]){
d[t][u.F] = d[t][v] + u.S;
dfs(u.F, t);
}
}
return;
}
int travelTime(int N, int M, int L, int A[], int B[], int T[]) {
for(ll i = 0; i < M; i++){
g[A[i]].pb(Mp(B[i], T[i]));
g[B[i]].pb(Mp(A[i], T[i]));
}
ll mx = 0;
vector<ll> a;
for(ll i = 0; i < N; i++){
if(vis1[i]) continue;
vec.clear();
dfs1(i);
d[0][i] = 0;
dfs(i, 0);
ll v = vec[0];
for(ll u : vec){
vis[u] = 0;
if(d[0][u] > d[0][v]) v = u;
}
d[1][v] = 0;
dfs(v, 1);
ll x = vec[0];
for(ll u : vec){
vis[u] = 0;
if(d[1][u] > d[1][x]) x = u;
}
d[0][x] = 0;
dfs(x, 0);
ll r = inf;
for(ll u : vec){
vis[u] = 0;
ll dd = max(d[0][u], d[1][u]);
mx = max(mx, dd);
r = min(r, dd);
}
a.pb(r);
}
sort(all(a), greater<ll>());
if(Sz(a) > 1) mx = max(mx, a[0] + a[1] + L);
if(Sz(a) > 2) mx = max(mx, a[2] + a[1] + L + L);
return mx;
}
/*int main(){
fast_io;
int n, m, l, a[100], b[100], c[100];
cin >> n >> m >> l;
for(ll i = 0; i < m; i++){
cin >> a[i] >> b[i] >> c[i];
}
cout << travelTime(n, m, l, a, b, c);
return 0;
}*/
