#include "dreaming.h"
#include <bits/stdc++.h>
using namespace std;
//macros
typedef long long ll;
typedef pair<int, int> ii;
typedef pair<ll, ll> lll;
typedef tuple<int, int, int> iii;
typedef vector<int> vi;
typedef vector<ii> vii;
typedef vector<iii> viii;
typedef vector<ll> vll;
typedef vector<lll> vlll;
#define REP(a,b,c) for(int a=int(b); a<int(c); a++)
#define RE(a,c) REP(a,0,c)
#define RE1(a,c) REP(a,1,c+1)
#define REI(a,b,c) REP(a,b,c+1)
#define REV(a,b,c) for(int a=int(c-1); a>=int(b); a--)
#define INF 1e9
#define pb push_back
#define fi first
#define se second
const int MX = 3e5;
int n, m, l;
vii adj[MX];
ii len[MX];
bitset<MX> visited;
ii push(ii p, int v) {
return {max(p.fi,v), max(min(p.fi,v),p.se)};
}
void dfsSize(int u, int p=-1) {
visited[u] = 1;
len[u] = {0, 0};
for(ii v:adj[u]) if(v.fi!=p) dfsSize(v.fi,u), len[u] = push(len[u], v.se+len[v.fi].fi);
}
ii getShortest(int u, int p=-1, int top = 0) {
ii ans = {max(top, len[u].fi), u};
for(ii v:adj[u]) if(v.fi!=p) {
int nTop = v.se + top;
if(len[u].fi == v.se+len[v.fi].fi) nTop = max(nTop, v.se + len[u].se);
else nTop = max(nTop, v.se + len[u].fi);
ans = min(ans, getShortest(v.fi, u, nTop));
}
return ans;
}
ii dfsFurthest(int u, int p=-1, int d=0) {
ii ans = {d,u};
for(ii v:adj[u]) if(v.fi!=p) ans = max(ans, dfsFurthest(v.fi, u, v.se+d));
return ans;
}
int travelTime(int N, int M, int L, int A[], int B[], int T[]) {
n=N, m=M, l=L;
RE(i,m) adj[A[i]].pb({B[i], T[i]});
RE(i,m) adj[B[i]].pb({A[i], T[i]});
priority_queue<ii> pq;
visited.reset();
RE(u,n) {
if(visited[u]) continue;
dfsSize(u);
ii p = getShortest(u);
pq.push(p);
}
int u = pq.top().se; pq.pop();
while(!pq.empty()) {
int v = pq.top().se; pq.pop();
adj[u].pb({v, l});
adj[v].pb({u, l});
}
ii p = dfsFurthest(0);
return dfsFurthest(p.se).fi;
}
