#include "dreaming.h"
#include "bits/stdc++.h"
#define pb push_back
#define pii pair<int, int>
using namespace std;
using ll = long long;
const int MAXN = 100005;
vector<vector<pair<int, int> > > adj(MAXN);
bool vis[MAXN];
pair<ll, int> down[MAXN][2];
void dfs_down(int v, int p)
{
vis[v] = true;
down[v][0].second = down[v][1].second = -1;
//cout << v << "\n";
for(pii e : adj[v])
{
//cout << e.first << " " << e.second << "\n";
if(e.first == p)
continue;
dfs_down(e.first, v);
ll val = down[e.first][0].first + e.second;
if(down[v][0].first < val)
{
down[v][0].first = val;
down[v][0].second = e.first;
} else if(down[v][1].first < val)
{
down[v][1].first = val;
down[v][1].second = e.first;
}
}
//cout << v << " " << down[v] << "\n";
}
pair<ll, int> dfs_up(int v, int p, ll top)
{
vis[v] = true;
pair<ll, int> curr = {max(top, down[v][0].first), v};
if(down[v][0].second != -1)
{
pii e;
for(pii tmp : adj[v])
{
if(down[v][0].second == tmp.first)
e = tmp;
}
pair<ll, int> temp = dfs_up(down[v][0].second, v, max(top, down[v][1].first) + e.second);
if(curr.first > temp.first)
curr = temp;
}
return curr;
}
void dfs_check(int v, int p)
{
vis[v] = true;
for(pii e : adj[v])
{
if(e.first == p)
continue;
dfs_check(e.first, v);
}
}
vector<int> component;
void dfs_add(int v, int p)
{
component.pb(v);
for(pii e : adj[v])
{
if(e.first == p)
continue;
dfs_add(e.first, v);
}
}
ll dfs_slow(int v, int p)
{
vis[v] = true;
ll maxi = 0;
for(pii e : adj[v])
{
if(e.first == p)
continue;
ll yes = dfs_slow(e.first, v) + e.second;
maxi = max(yes, maxi);
}
return maxi;
}
ll ans = 0;
ll dfs_long(int v, int p)
{
ll max_temp = 0, max_1 = 0;
for(pii e : adj[v])
{
if(e.first == p)
continue;
ll temp = dfs_long(e.first, v) + e.second;
max_temp = max(max_temp, max_1 + temp);
max_1 = max(max_1, temp);
}
ans = max(ans, max_temp);
return max_1;
}
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], T[i]});
adj[B[i]].pb({A[i], T[i]});
}
for(int i = 0; i < N; i++)
{
//cout << i << "\n";
if(!vis[i])
dfs_down(i, -1);
//cout << i << "\n";
}
for(int i = 0; i < N; i++)
vis[i] = false;
vector< pair<ll, int> > root_nodes;
for(int i = 0; i < N; i++)
{
if(!vis[i])
{
//cout << i << "\n";
dfs_add(i, -1);
pair<ll, int> temp = {1e9+5, 0};
for(int e : component)
{
//cout << e << "\n";
ll tmp_big = dfs_slow(e, -1);
if(tmp_big <= temp.first)
temp = {tmp_big, e};
}
//pair<ll, int> temp = dfs_up(i, -1, 0);
//dfs_check(i, -1);
//cout << i << " " << temp.first << " " << temp.second << "\n";
root_nodes.pb(temp);
}
component.clear();
}
sort(root_nodes.begin(), root_nodes.end());
reverse(root_nodes.begin(), root_nodes.end());
int from = root_nodes[0].second;
//cout << root_nodes.size() << "\n";
for(int i = 1; i < root_nodes.size(); i++)
{
int to = root_nodes[i].second;
adj[from].pb({to, L});
adj[to].pb({from, L});
//cout << from << " " << to << "\n";
}
dfs_long(0, -1);
return ans;
}
