#include "dreaming.h"
//#include "grader.h"
#include <bits/stdc++.h>
using namespace std;
#define m_p make_pair
#define fi first
#define se second
#define sz(x) ((int)(x).size())
#define all(x) (x).begin(),(x).end()
const int N = 100005, INF = 1000000009;
int ans;
int n;
vector<pair<int, int> > g[N];
bool c[N];
int dp[N];
void dfs0(int x, int p)
{
c[x] = true;
dp[x] = 0;
for (int i = 0; i < g[x].size(); ++i)
{
int h = g[x][i].fi;
if (h == p)
continue;
dfs0(h, x);
dp[x] = max(dp[x], dp[h] + g[x][i].se);
}
}
int minu;
void dfs1(int x, int p, int dpp)
{
int max1 = 0, max2 = 0;
for (int i = 0; i < g[x].size(); ++i)
{
int h = g[x][i].fi;
if (h == p)
{
if (dpp + g[x][i].se >= max1)
{
max2 = max1;
max1 = dpp + g[x][i].se;
}
else if (dpp + g[x][i].se >= max2)
max2 = dpp + g[x][i].se;
continue;
}
if (dp[h] + g[x][i].se >= max1)
{
max2 = max1;
max1 = dp[h] + g[x][i].se;
}
else if (dp[h] + g[x][i].se >= max2)
max2 = dp[h] + g[x][i].se;
}
ans = max(ans, max1 + max2);
minu = min(minu, max1);
for (int i = 0; i < g[x].size(); ++i)
{
int h = g[x][i].fi;
if (h == p)
continue;
if (dp[h] + g[x][i].se == max1)
dfs1(h, x, max2);
else
dfs1(h, x, max1);
}
}
int travelTime(int N, int M, int L, int A[], int B[], int T[])
{
for (int i = 0; i < M; ++i)
{
int x = A[i];
int y = B[i];
int z = T[i];
g[x].push_back(m_p(y, z));
g[y].push_back(m_p(x, z));
}
multiset<int> s;
for (int x = 0; x < N; ++x)
{
if (c[x])
continue;
dfs0(x, x);
minu = INF;
dfs1(x, x, 0);
s.insert(minu);
}
while (sz(s) > 1)
{
int x = *s.begin();
s.erase((s.begin()));
int y = *(--s.end());
s.erase((--s.end()));
ans = max(ans, x + L + y);
int minu = min(max(x, L + y), max(x + L, y));
s.insert(minu);
}
return ans;
}
