#pragma once
#include "dreaming.h"
#include <bits/stdc++.h>
using namespace std;
// Loops
#define FOR(n) for(int i=0;i<n;i++)
#define FORJ(n) for(int j=0;j<n;j++)
#define FORN(n,x) for(int x=0;i<n;i++)
#define RFOR(n) for(int i=n-1;i>=0;i--)
#define RFORN(n,x) for(int x=n-1;x>=0;x--)
#define ODD_FOR(n) for(int i=1;i<n;i+=2)
#define EVEN_FOR(n) for(int i=2;i<n;i+=2)
#define FROM(n,m) for(int i=n;i<m;i++)
#define FROMJ(n,m) for(int j=n;j<m;j++)
#define RFROM(n,m) for(int i=n-1;i>=m;i--)
#define RFROMJ(n,m) for(int j=n-1;j>=m;j--)
#define STL_FOR(a) for(auto i=a.begin();i!=a.end();i++)
#define STL_FORJ(a) for(auto j=a.begin();j!=a.end();j++)
#define STL_FORN(a,x) for(auto x=a.begin();x!=a.end();x++)
#define STL_FROM(a,n,m) for(auto i=n;i!=m;i++)
#define STL_FROMJ(n,m) for(auto j=n;j!=m;j++)
#define RSTL_FOR(a) for(auto i=a.rbegin();i!=a.rend();i++)
#define RSTL_FORJ(a) for(auto j=a.rbegin();j!=a.rend();j++)
// Types
#define ll long long int
#define vec vector
#define veci vector<int>
#define pb push_back
#define pf push_front
#define fi first
#define se second
#define umap unordered_map
#define ummap unordered_multimap
#define mmap multimap
#define mset multiset
#define uset unordered_set
#define umset unordered_multiset
#define endl '\n'
#define all(a) a.begin(), a.end()
// I/O
void read() {}
template<typename type, typename... types>
void read(type& arg, types&... args) { cin >> arg; read(args...); }
void write() { cout << endl; }
template<typename type, typename... types>
void write(type arg, types... args) { cout << arg << ' '; write(args...); }
#define dbg(x) cerr<<#x<<" = "<<x<<endl;
struct weighted_edge {
int edge, weight;
};
struct graph {
int n, m;
list<weighted_edge>* adj;
graph(int n, int m)
:n(n), m(m)
{
adj = new list<weighted_edge>[n];
}
~graph() { delete[] adj; }
void add_edge(int node, int edge, int weight) {
adj[node].push_back({ edge, weight });
adj[edge].push_back({ node, weight });
}
friend istream& operator>> (istream& in, graph& g) {
int node, edge, weight;
for (int i = 0; i < g.m; i++) {
in >> node >> edge >> weight;
g.add_edge(node, edge, weight);
}
return in;
}
};
const int M = 1e6;
struct node_dist {
int node, dist = 0;
};
struct two_max {
node_dist fi, se;
void add(int n, int d) {
if (fi.dist < d) {
se = fi;
fi = { n, d };
}
else if (se.dist < d) {
se = { n, d };
}
}
};
two_max node_max_dist[M];
int graph_min_dist = INT_MAX;
int graph_min_node = -1;
int max_dist=-1;
bool seen[M] = {};
int billabong_front(graph& g, int node, int edge) {
seen[edge] = true;
for (weighted_edge x : g.adj[edge]) {
if (x.edge != node) {
node_max_dist[edge].add(x.edge, billabong_front(g, edge, x.edge) + x.weight);
}
}
return node_max_dist[edge].fi.dist;
}
void billabong_back(graph& g, int node, int edge) {
list<pair<int, int>> q;
q.push_front({node, edge});
while (!q.empty()) {
node = q.front().fi;
edge = q.front().se;
q.pop_front();
if (graph_min_dist > node_max_dist[edge].fi.dist) {
graph_min_dist = node_max_dist[edge].fi.dist;
graph_min_node = edge;
}
for (weighted_edge x : g.adj[edge]) {
if (x.edge != node) {
if (node_max_dist[edge].fi.node != x.edge) {
node_max_dist[x.edge].add(edge, node_max_dist[edge].fi.dist + x.weight);
}
else {
node_max_dist[x.edge].add(edge, node_max_dist[edge].se.dist + x.weight);
}
max_dist = max(max_dist, node_max_dist[x.edge].fi.dist + node_max_dist[x.edge].se.dist);
q.push_front({edge, x.edge});
}
}
}
}
inline void billabong(graph& g, int node) {
billabong_front(g, -1, node);
billabong_back(g, -1, node);
}
void insert(int a[3], int x) {
if (a[0] < x) {
a[2] = a[1];
a[1] = a[0];
a[0] = x;
}
else if (a[1] < x) {
a[2] = a[1];
a[1] = x;
}
else if (a[2] < x) {
a[2] = x;
}
}
int travelTime(int n, int m, int l, int A[], int B[], int T[]) {
graph g(n, m);
FOR(m) {
g.add_edge(A[i], B[i], T[i]);
}
int a[3] = { -l, -l, -l };
FOR(n) {
if (!seen[i]) {
graph_min_dist = INT_MAX;
billabong(g, i);
insert(a, graph_min_dist);
}
}
return max(max_dist, max(a[0]+a[1]+l, a[1]+a[2]+l+l));
}
