#include<bits/stdc++.h>
#include "dreaming.h"
#define fi first
#define se second
using namespace std;
using ll = long long;
const int N = 2e5;
int par[N+5];
vector<pair<int,int>> g[N+5];
bool f[N+5];
ll d[2][N+5];
vector<int> V;
pair<ll,ll> G[N+5];
int fba(int x){
return par[x] == x ? x : par[x] = fba(par[x]);
}
void join(int x,int y){
//cout << x << ',' << y << "!\n";
x = fba(x);
y = fba(y);
if(x != y){
par[y] = x;
}
}
pair<int,ll> dfs(int x,int p,ll dist,int ty){
if(ty == 1)
V.push_back(x);
pair<int,ll> mx = {x,dist};
d[ty][x] = dist;
for(pair<int,int> i : g[x]) if(i.fi != p){
pair<int,ll> tmp = dfs(i.fi,x,(ll)dist + i.se,ty);
if(tmp.se > mx.se) mx = tmp;
}
return mx;
}
int travelTime(int n,int m,int l,int a[],int b[],int t[]){
for(int i = 0 ; i < n ; ++i) par[i] = i;
for(int i = 0 ; i <= m ; ++i){
g[a[i]].push_back({b[i],t[i]});
g[b[i]].push_back({a[i],t[i]});
join(a[i],b[i]);
}
// cout << fba(1) << ',' << fba(2) << "!\n";
// cout << "?\n";
int n1 = 0;
for(int i = 0 ; i < n ; ++i){
int pos = fba(i);
if(f[pos]) continue;
//cout << i << ',' << pos << ":\n";
V.clear();
pair<int,int> t = dfs(pos,pos,0,0);
pair<int,int> t1 = dfs(t.fi,t.fi,0,1);
dfs(t1.fi,t1.fi,0,0);
// cout << t.fi << ' ' << t1.fi << ' ' << t1.se << '\n';
n1++;
f[pos] = 1;
G[n1] = {-1,-1};
for(int j : V){
int w1 = d[0][j];
int w2 = d[1][j];
if(w1 > w2) swap(w1,w2);
//cout << j << ' ' << w1 << ' ' << w2 << '\n';
d[0][j] = d[1][j] = 0;
if(G[n1].se == -1 || G[n1].fi + G[n1].se > w1 + w2 || (w1 + w2 == G[n1].fi + G[n1].se && G[n1].se < w1)) G[n1] = {w2,w1};
}
//cout << G[n1].fi << ' ' << G[n1].se << "!\n";
}
//cout << "??\n";
sort(G+1,G+1+n1,greater<pair<ll,ll>>());
// for(int i = 1 ; i <= n1 ; ++i)
// cout << G[i].fi << ' ' << G[i].se << "\n";
pair<ll,ll> mx = G[1];
for(int i = 2 ; i <= n1 ; ++i){
if(G[i].fi + l > mx.se){
mx.se = G[i].fi + l;
if(mx.se > mx.fi) swap(mx.fi,mx.se);
}
}
return mx.fi + mx.se;
}
//int main(){
// int n,m,l;
// cin >> n >> m >> l;
// int a[m+1],b[m+1],t[m+1];
// for(int i = 1 ; i <= m ; ++i) cin >> a[i] >> b[i] >> t[i];
//
// cout << travel_time(n,m,l,a,b,t);
//}
