#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}); } int odp=0; vec<int> pom; 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; } } for(const auto &a:wie) { dst[a]=0; } dfsDiam(root, -1); int tail=root; for(const auto &a:wie) { if(dst[a]>dst[tail]) { tail=a; } } vec<int> diamWie={tail}; vec<int> diamDst; int cur=tail; int sumDst=0; while(par[cur].fi>0) { // t>=1 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; for(int i=0; i<sz(diamWie); ++i) { if(max(l, r)<bst) { bst=max(l, r); } if(i+1<sz(diamWie)) { l+=diamDst[i]; r-=diamDst[i]; } } pom.pb(bst); } } sort(all(pom), greater<>()); if(sz(pom)>=2) { ckmax(odp, pom[0]+L+pom[1]); } if(sz(pom)>=3) { ckmax(odp, pom[1]+2*L+pom[2]); } 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