#include <bits/stdc++.h>
#include "dreaming.h"
using namespace std;
typedef long long ll;
const ll MAXN = 1e5 + 10;
const ll INF = 4e18 + 10;
struct edge
{
ll u,v,cost;
edge(){};
edge(ll _u, ll _v, ll _cost)
{
u = _u;
v = _v;
cost = _cost;
}
edge(ll _v, ll _cost)
{
u = v = _v;
cost = _cost;
}
bool operator<(const edge&e)const
{
return cost < e.cost;
}
};
ll n,m,l;
vector < edge > adj[MAXN];
bool visited[MAXN];
ll len[MAXN];
ll opt1[MAXN];
ll opt2[MAXN];
ll real_distance;
ll border;
vector < ll > topo;
void dfs(ll u, ll par)
{
topo.push_back(u);
visited[u] = true;
for(edge e : adj[u])
if(e.v != par)
dfs(e.v, u);
}
void find_opt(ll u, ll par)
{
opt1[u] = 0;
for(edge e : adj[u])
{
ll v = e.v;
ll cost = e.cost;
if(v == par)
continue;
find_opt(v, u);
ll cur = opt1[v] + cost;
if(cur > opt1[u])
{
opt2[u] = opt1[u];
opt1[u] = cur;
}
else
{
opt2[u] = max(opt2[u], cur);
}
}
}
void find_dist(ll u, ll par, ll carry)
{
ll cur = max(carry, opt1[u]);
real_distance = min(real_distance, cur);
if(carry >= opt1[u])
return;
for(edge e : adj[u])
{
ll v = e.v;
ll cost = e.cost;
if(v == par)
continue;
if(opt1[u] == opt1[v] + e.cost)
{
ll new_carry = max(carry, opt2[u]) + cost;
find_dist(v, u, new_carry);
return; /// prawa rekursiq !!!
}
}
}
void find_path(ll src)
{
for(ll u : topo)
{
len[u] = INF;
}
len[src] = 0;
queue < ll > q;
q.push(src);
while(!q.empty())
{
ll u = q.front();
q.pop();
for(edge e : adj[u])
{
ll v = e.v;
ll cost = e.cost;
if(len[v] == INF) /// unvisited
{
len[v] = len[u] + cost;
q.push(v);
}
}
}
}
void init(ll u)
{
topo.clear();
dfs(u, u);
real_distance = INF;
find_opt(u, u);
find_dist(u, u, 0);
find_path(u);
}
ll solve(ll u)
{
init(u);
ll opt_ver = u;
for(ll v : topo)
if(len[v] > len[opt_ver])
opt_ver = v;
find_path(opt_ver);
for(ll v : topo)
if(len[v] > border)
border = len[v];
return real_distance;
}
ll solution()
{
vector < ll > dists;
for(int i = 0; i < n; i++)
{
if(!visited[i])
{
ll cur_dist = solve(i);
dists.push_back(cur_dist);
}
}
sort(dists.begin(), dists.end());
ll comp_cnt = dists.size();
ll ans = dists[comp_cnt - 1] + dists[comp_cnt - 2] + l;
if(comp_cnt >= 3)
{
ans = max(ans, dists[comp_cnt - 2] + dists[comp_cnt - 3] + 2 * l);
}
ans = max(ans, border);
return ans;
}
int travelTime(int N, int M, int L, int a[], int b[], int w[])
{
n = N;
m = M;
l = L;
for(int i = 0; i < m; i++)
{
adj[a[i]].push_back(edge(a[i], b[i], w[i]));
adj[b[i]].push_back(edge(b[i], a[i], w[i]));
}
return solution();
}
