#include "dreaming.h"
#include <algorithm>
#include <iostream>
#include <queue>
#include <utility>
#include <vector>
#include <map>
using namespace std;
#define pb push_back
long long a, b, c, d, h, n, m, x, y;
map<pair<int, int>, int> weight;
vector<int> adj[1000000];
vector<bool> vis(1000000);
vector<int> par(1000000);
long long maxdist;
vector<int> component;
void dfs(int node, long long dist) {
vis[node] = 1;
component.pb(node);
if(dist > maxdist) {
maxdist = dist;
h = node;
}
for(auto j : adj[node]) {
if(!vis[j]) {
par[j] = node;
dfs(j, dist+weight[{node, j}]);
}
}
}
int travelTime(int N, int M, int L, int A[], int B[], int T[]) {
for(int i = 0; i<M; i++) {
adj[A[i]].pb(B[i]);
adj[B[i]].pb(A[i]);
weight[{A[i], B[i]}] = T[i];
weight[{B[i], A[i]}] = T[i];
}
vector<long long> all;
long long ans = 0;
for(int i = 0; i<N; i++) {
if(!vis[i]) {
// cout << i << " ";
h = i;
maxdist = 0;
component.clear();
dfs(i, 0);
for(auto j : component) {
par[j] = 0;
vis[j] = 0;
}
maxdist = 0;
x = h;
component.clear();
dfs(x, 0);
vector<int> path;
long long tt = 0;
while(h != x) {
path.pb(weight[{h, par[h]}]);
tt += weight[{h, par[h]}];
h = par[h];
}
y = 100000000000000000;
h = 0;
for(int j = 0; j<path.size(); j++) {
h += path[j];
y = min(y, (long long)max(h, tt-h));
}
ans = max(ans, tt);
// cout << y << "\n";
if(y==100000000000000000) {
all.pb(0);
}
else all.pb(y);
}
}
sort(all.rbegin(), all.rend());
if(all.size()==1) {
return ans;
}
// for(auto j : all) cout << j << " ";
ans = max(ans, all[0] + all[1] + L);
if(all.size() > 2) {
ans = max(ans, all[1]+all[2]+L+L);
}
return ans;
}
// int32_t main() {
// ios::sync_with_stdio(false);
// cout.tie(0); cin.tie(0);
// int n, m, l;
// cin >> n >> m >> l;
// int A[m], B[m], C[m];
// for(int i = 0; i<m; i++) {
// cin >> A[i] >> B[i] >> C[i];
// }
// cout << travelTime(n, m, l, A, B, C);
// return 0;
// }
