#include "dreaming.h"
#include <bits/stdc++.h>
//#define respagold ios_base::sync_with_stdio(0), cin.tie(0);
//#define int long long
#define ll long long
#define int2 __int128_t
#define FOR( i, x, n, d ) for( int i = x; i <= n; i += d )
#define FORR( i, x, n, d ) for( int i = x; i >= n; i -= d )
#define F first
#define S second
#define all(x) x.begin(), x.end()
#define sz(x) (int)(x.size())
#define pb push_back
#define pf push_front
#define ins insert
#define lb lower_bound
#define ub upper_bound
#define pii pair <int, int>
#define ppi pair <pair <int, int>, int>
#define pip pair <int, pair <int, int>>
#define mkp make_pair
using namespace std;
const int N = 2e5 + 12;
const int inf = 2e9;
const int mod = 1e9 + 7;
const double eps = 1e-20;
int n, m, l, x, y, w, mn, mxd, d[N], used[N];
vector <pii> g[N]; vector <int> ve;
multiset <int> st[N];
void dfs( int v, int p = 0 )
{
for( auto to : g[v] )
{
if( to.F != p )
{
dfs( to.F, v ); st[v].ins(d[to.F] + to.S);
d[v] = max(d[v], d[to.F] + to.S);
}
}
ve.pb(v);
}
void dfs2( int v, int p = 0, int up = 0 )
{
mn = min(mn, max(d[v], up));
for( auto to : g[v] )
{
if( to.F != p )
{
st[v].erase(st[v].find(d[to.F] + to.S)); int nw = up;
if(!st[v].empty()) nw = max(nw, *st[v].rbegin());
st[v].ins(d[to.F] + to.S);
dfs2(to.F, v, nw + to.S);
}
}
used[v] = 1;
}
int dist( int v, int p = 0 )
{
dfs(v);
int mx = -inf, id;
for( auto i : ve )
{
if( d[i] > mx ) mx = d[i], id = i;
d[i] = 0, st[i].clear();
}
ve.clear(), dfs(id);
for( auto i : ve )
{
if( d[i] > mx ) mx = d[i];
d[i] = 0, st[i].clear();
}
ve.clear();
return mx;
}
int travelTime( int N, int M, int L, int A[], int B[], int T[] )
{
n = N, m = M, l = L;
FOR( i, 0, m - 1, 1 )
{
x = A[i], y = B[i], w = T[i];
x ++, y ++;
g[x].pb({y, w});
g[y].pb({x, w});
}
vector <int> vals;
FOR( i, 1, n, 1 )
{
if( !used[i] )
{
mxd = max(mxd, dist(i));
mn = inf;
dfs(i), dfs2(i);
vals.pb(mn);
}
}
sort( all(vals) );
reverse( all(vals) );
if( sz(vals) == 1 ) return mxd;
else if( sz(vals) == 2 ) return max(mxd, vals[0] + vals[1] + l);
else return max({ mxd, vals[0] + vals[1] + l, vals[1] + vals[2] + 2 * l });
}
/*
signed main()
{
//respagold
int test = 1;
if( !test ) cin >> test;
while( test -- ) solve();
}*/
