#include<bits/stdc++.h>
#include "dreaming.h"
using namespace std;
#define foreach(it, x) for(type(x) it = x.begin(); it != x.end(); it++)
#define type(x) __typeof(x.begin())
#define pb push_back
#define mp make_pair
#define nd second
#define st first
const int N = 1e6 + 5;
const int inf = 1e9 + 5;
typedef pair< int , int > pii;
int n, m, x, y, z, val[N], h[N];
vector< pii > v[N];
pii dfs(int node, int root = 0) {
pii tt = mp(0, node);
foreach(it, v[node])
if(it->st != root) {
pii temp = dfs(it->st, node);
temp.st += it->nd;
tt = max(tt, temp);
}
return tt;
}
void dfs2(int node, int root = 0, int dist = 0) {
val[node] = max(val[node], dist);
foreach(it, v[node])
if(it->st != root)
dfs2(it->st, node, dist + it->nd);
}
int take(int node, int root = 0) {
int nnn = node;
h[node] = 1;
foreach(it, v[node])
if(it->st != root) {
int ttt = take(it->st, node);
if(val[ttt] < val[nnn])
nnn = ttt;
}
return nnn;
}
int travelTime(int N, int M, int L, int A[], int B[], int T[]) {
n = N;
val[n] = inf * 2;
for(int i = 0; i < M; i++) {
int x = A[i], y = B[i], z = T[i];
v[x].pb(mp(y, z));
v[y].pb(mp(x, z));
}
priority_queue< pii > q;
for(int i = 0; i < N; i++) {
if(!h[i]) {
int x = dfs(i).nd, y = dfs(x).nd;
dfs2(x); dfs2(y);
int nnn = take(i);
q.push(mp(val[nnn], nnn));
}
}
while(q.size() > 1) {
pii t1 = q.top(); q.pop();
pii t2 = q.top(); q.pop();
int q1 = max(t1.st, t2.st + L);
int q2 = max(t1.st + L, t2.st);
v[t1.nd].pb(mp(t2.nd, L));
v[t2.nd].pb(mp(t1.nd, L));
pii tt;
if(q1 < q2) q.push(tt =mp(q1, t1.nd));
else q.push(tt = mp(q2, t2.nd));
}
int x = dfs(0).nd, ans = dfs(x).st;
return ans;
}
