#include <bits/stdc++.h> // #include <ext/pb_ds/assoc_container.hpp> using namespace std; // using namespace __gnu_pbds; // template <typename T> // using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>; #define int long long #define pb push_back #define eb emplace_back #define pf push_front #define ppb pop_back #define ppf pop_front #define ins insert #define ff first #define ss second // mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count()); constexpr int inf = 1e15, mod = 998244353, maxn = 1000005; vector<vector<pair<int, int>>> g; vector<bool> vis; vector<int> dist; vector<vector<int>> comp; void dfs(int u, int p, int col){ vis[u]=true; comp[col].pb(u); for (auto [v, w]: g[u]){ if (v !=p){ dist[v]=dist[u]+w; dfs(v, u, col); } } } void dfs2(int u, int p){ for (auto [v, w]:g[u]){ if (v != p){ dist[v]=dist[u]+w; dfs2(v, u); } } } void dfs3(int u, int p, map<int,int>&dist){ for (auto [v, w]:g[u]){ if (v != p){ dist[v]=dist[u]+w; dfs3(v, u, dist); } } } int best(int col){ int a = *comp[col].begin(), b, c; dist[a]=0; dfs2(a, -1); int mx=-inf; for (int v: comp[col]){ if (dist[v]>mx){ mx=dist[v]; b=v; } } dist[b] = 0; dfs2(b,-1); mx=-inf; for (int v: comp[col]){ if (dist[v]>mx){ mx=dist[v]; c=v; } } map<int, int> distC; distC[c] = 0; dfs3(c,-1,distC); int mn = inf; for (int u: comp[col]){ mn = min(mn, max(1ll*dist[u],1ll*distC[u])); } return mn; } extern "C" int travelTime(int n, int m, int l, int a[],int b[],int t[]){ g.assign(n+1, vector<pair<int,int>>()); vis.assign(n+1, false); dist.assign(n+1, -inf); comp.assign(n+1, vector<int>()); for (int i = 0; i < m; i++){ g[a[i]].eb(b[i], t[i]); g[b[i]].eb(a[i], t[i]); } int d=-inf, col=0; for (int i = 0; i < n; i++){ if (!vis[i]){ dist[i] = 0; dfs(i,-1, col); int u, mx=-inf; for (int v: comp[col]){ if (dist[v]>mx){ mx=dist[v]; u=v; } } dist[u] = 0; dfs2(u,-1); mx=-inf; for (int v: comp[col]){ if (dist[v]>mx){ mx=dist[v]; } } d = max(d, mx); col++; } } vector<int> r; for (int i = 0; i < col; i++){ r.pb(best(i)); } sort(r.rbegin(), r.rend()); if (col==1){ return d; } else if (col==2){ return max(d, r[0]+r[1]+l); } else{ return max({d, r[0]+r[1]+l, r[1]+l+l+r[2]}); } } /* void solve(){ int n,m, l; cin >> n >> m >> l; int a[m], b[m], t[m]; for (int i = 0; i < m; i++){ cin >> a[i] >> b[i] >> t[i]; } cout << travelTime(n, m, l, a, b, t) << '\n'; } signed main(){ ios::sync_with_stdio(false); cin.tie(nullptr); int t = 1; // cin >> t; for (int i = 0; i < t; i++) { solve(); } return 0; } */