#include<bits/stdc++.h>
#include "dreaming.h"
using namespace std;
#define FOR(i, a, b) for (int i = (a), _b = (b); i <= _b; i++)
#define FORD(i, a, b) for (int i = (a), _b = (b); i >= _b; i--)
#define fi first
#define se second
#define pb push_back
#define ALL(a) (a).begin(), (a).end()
#define task "kbsiudthw"
typedef vector<int> vi;
typedef pair<int, int> ii;
typedef pair<int, ii> pii;
const int N = 1e5 + 5;
const int INF = 0x3f3f3f3f;
const int MOD = 1e9 + 2277;
int n, m, L, dp[N], mx[N], mi[N], scc;
vector<ii> G[N];
void dfs(int u, int par){
dp[u] = 0;
for (ii &v : G[u]){
if (v.fi == par) continue;
dfs(v.fi, u);
dp[u] = max(dp[u], dp[v.fi] + v.se);
}
}
void reroot(int u, int par){
mi[scc] = min(mi[scc], dp[u]);
mx[scc] = max(mx[scc], dp[u]);
vector<ii> nodes; nodes.pb({0,0});
for (ii &x : G[u]) nodes.pb(x);
vi pref, suff;
pref = suff = vi(nodes.size() + 3, 0);
FOR (i, 1, (int)nodes.size() - 1) pref[i] = max(pref[i-1], dp[nodes[i].fi] + nodes[i].se);
FORD(i, (int)nodes.size() - 1, 1) suff[i] = max(suff[i+1], dp[nodes[i].fi] + nodes[i].se);
FOR (i, 1, (int)nodes.size() - 1){
int v = nodes[i].fi;
if (v == par) continue;
dp[u] = max(pref[i-1], suff[i+1]);
dp[v] = max(dp[v], dp[u] + nodes[i].se);
reroot(v, u);
}
dp[u] = pref[(int)nodes.size() - 1];
}
int travleTime(int n, int m, int L, int A[], int B[], int T[]){
FOR (i, 0, m-1){
++A[i]; ++B[i];
G[A[i]].pb({B[i], T[i]});
G[B[i]].pb({A[i], T[i]});
}
memset(dp, -1, sizeof dp);
multiset<ii> s;
FOR(i, 1, n) {
if (~dp[i]) continue;
++scc;
mi[scc] = 1e18;
dfs(i, 0);
reroot(i, 0);
s.insert({mi[scc], mx[scc]});
}
while (s.size() > 1){
auto it = *s.begin(); s.erase(s.begin());
auto it2 = *s.rbegin(); s.erase(--s.end());
ii nw;
nw.se = max({it.second, it2.second, it.first + it2.first + L});
nw.fi = min({max(it.first, it2.first + L), max(it2.first, it.first + L)});
s.insert(nw);
}
return s.begin()->second;
}
//signed main(){
// ios_base::sync_with_stdio(0);
// cin.tie(0); cout.tie(0);
// if (fopen(task".inp", "r")){
// freopen(task".inp", "r", stdin);
// freopen(task".out", "w", stdout);
// }
// cin >> n >> m >> L;
// FOR (i, 1, m){
// int u, v, w; cin >> u >> v >> w;
// ++u;
// ++v;
// G[u].pb({v, w});
// G[v].pb({u, w});
// }
// memset(dp, -1, sizeof dp);
// multiset<ii> s;
//
// FOR(i,1 , n) {
// if (~dp[i]) continue;
// ++scc;
// mi[scc] = 1e18;
// dfs(i, 0);
// reroot(i, 0);
// s.insert({mi[scc], mx[scc]});
// }
//
// while (s.size() > 1){
// auto it = *s.begin(); s.erase(s.begin());
// auto it2 = *s.rbegin(); s.erase(--s.end());
// ii nw;
// nw.se = max({it.second, it2.second, it.first + it2.first + L});
// nw.fi = min({max(it.first, it2.first + L), max(it2.first, it.first + L)});
// s.insert(nw);
// }
// cout << s.begin()->second;
//
// return 0;
//}
