#include <bits/stdc++.h> using namespace std; using ll=long long; template <typename T> using vec=vector<T>; template <typename T> inline void ckmax(T& a, const T& b) { if(a<b) { a=b; } } template <typename T> inline void ckmin(T& a, const T& b) { if(a>b) { a=b; } } constexpr char nl='\n'; #define fi first #define se second #define pb push_back #define sz(c) (int)(c).size() #define all(c) c.begin(),c.end() #define rep(a, b) for(decltype(b) a=0; a<b; ++a) #ifdef LOCAL #define DEBUG 1 #else #define DEBUG 0 #endif #define ifbug if constexpr(DEBUG) #define bug(...) ifbug{cerr<<"["#__VA_ARGS__"]: ";bug__(__VA_ARGS__);cerr<<'\n';} template <typename...A> void bug__(A&&...a){((cerr<<a<<' '),...);} struct DebugStream { template <typename T> constexpr DebugStream& operator<<(T&& value) const { ifbug std::cerr<<std::forward<T>(value); return const_cast<DebugStream&>(*this); } }; inline constexpr DebugStream cbug{}; #ifndef LOCAL #include "dreaming.h" #endif constexpr int MAX_N=1e5; vec<pair<int, int>> adj[MAX_N]; bool vis[MAX_N]; int dst[MAX_N]; pair<int, int> par[MAX_N]; // {cost, parent} void dfsDist(int a, int p, vec<int> &wie) { wie.pb(a); vis[a]=true; for(const auto &[t, b]:adj[a]) { if(b!=p) { dst[b]=dst[a]+t; dfsDist(b, a, wie); } } } void dfsDiam(int a, int p) { for(const auto &[t, b]:adj[a]) { if(b!=p) { par[b]={t, a}; dst[b]=dst[a]+t; dfsDiam(b, a); } } } int travelTime(int N, int M, int L, int A[], int B[], int T[]) { rep(i, M) { int a=A[i]; int b=B[i]; int t=T[i]; adj[a].pb({t, b}); adj[b].pb({t, a}); } priority_queue<pair<int, int>> pq; int odp=0; for(int rt1=0; rt1<N; ++rt1) { if(!vis[rt1]) { // szukaj srednice vec<int> wie; dfsDist(rt1, -1, wie); int root=rt1; for(const auto &a:wie) { if(dst[a]>dst[root]) { root=a; } dst[a]=0; } dfsDiam(root, -1); int tail=root; for(const auto &a:wie) { if(dst[a]>dst[tail]) { tail=a; } } // bug(root, tail, par[root].fi, par[root].se, par[tail].fi, par[tail].se); vec<int> diamWie={tail}; vec<int> diamDst; int cur=tail; int sumDst=0; while(par[cur].fi>0) { // t>=1 // bug(cur, par[cur].fi); diamWie.pb(par[cur].se); diamDst.pb(par[cur].fi); sumDst+=par[cur].fi; cur=par[cur].se; } ckmax(odp, sumDst); // znajdz punkt balansowania // int bal=diamWie.front(); int bst=sumDst; int l=0; int r=sumDst; pair<int, int> maxPaths={r, l}; for(int i=0; i<sz(diamWie); ++i) { // bug(diamWie[i], l, r, bst); if(max(l, r)<bst) { // bal=diamWie[i]; bst=max(l, r); maxPaths={max(l, r), min(l, r)}; } if(i+1<sz(diamWie)) { l+=diamDst[i]; r-=diamDst[i]; } } pq.push(maxPaths); // bug(bal, bst, maxPaths.fi, maxPaths.se); } } while(sz(pq)>1) { auto x=pq.top(); pq.pop(); auto y=pq.top(); pq.pop(); // bug(x.fi, x.se, y.fi, y.se); vec<int> xPaths={x.fi, x.se, y.fi+L}; vec<int> yPaths={y.fi, y.se, x.fi+L}; sort(all(xPaths), greater<>()); sort(all(yPaths), greater<>()); ckmax(odp, xPaths[0]+xPaths[1]); ckmax(odp, yPaths[0]+yPaths[1]); pair<int, int> z={0, 0}; if(xPaths[0]<=yPaths[0]) { z={xPaths[0], xPaths[1]}; } else { z={yPaths[0], yPaths[1]}; } // bug(z.fi, z.se); pq.push(z); } return odp; } #ifdef LOCAL namespace grader { static int A[MAX_N]; static int B[MAX_N]; static int T[MAX_N]; void testCase() { int N, M, L; cin>>N>>M>>L; rep(i, M) { cin>>A[i]>>B[i]>>T[i]; } int ans=travelTime(N, M, L, A, B, T); cout<<ans<<nl; } } int32_t main() { cin.tie(0)->sync_with_stdio(0); grader::testCase(); } #endif