#include <iostream>
#include <cstdio>
#include <vector>
#include <algorithm>
#include <cstring>
#include <dreaming.h>
using namespace std;
#define ff first
#define ss second
#define mp make_pair
#define pb push_back
#define trace(x) cerr << #x << " " << x << endl
const int N = 1e5+11;
int n, m, l;
vector <pair <int, int> > ls[N];
int bio[N];
pair <int, int> maxi;
pair <int, int> mama[N];
int res = 0;
vector <int> v;
void dfs (int x, int dalj) {
bio[x] = 1;
maxi = max(maxi, mp(dalj, x));
for (int i=0;i<ls[x].size();i++) {
if (bio[ls[x][i].ff]) continue;
dfs(ls[x][i].ff, dalj + ls[x][i].ss);
}
}
void dfss (int x, int p, int dalj) {
maxi = max(maxi, mp(dalj, x));
mama[x].ff = p;
for (int i=0;i<ls[x].size();i++) {
if (ls[x][i].ff == p) {
mama[x].ss = ls[x][i].ss;
continue;
}
dfss (ls[x][i].ff, x, dalj+ls[x][i].ss);
}
}
int gore (int x, int dalj, int dm) {
int ret = max(dalj, dm-dalj);
if (mama[x].ff == -1) return ret;
ret = min(ret, gore (mama[x].ff, dalj+mama[x].ss, dm));
return ret;
}
int travelTime (int n, int m, int l, int a[N], int b[N], int t[N]) {
for (int i=0;i<m;i++) {
ls[a[i]].pb(mp(b[i], t[i]));
ls[b[i]].pb(mp(a[i], t[i]));
}
for (int i=0;i<n;i++) {
maxi = mp(0, 0);
if (bio[i]) continue;
dfs(i, 0);
int x = maxi.ss;
maxi = mp(0, 0);
dfss(x, -1, 0);
int y = maxi.ss;
int dm = maxi.ff;
res = max(res, dm);
v.pb(gore(y, 0, dm));
}
sort (v.begin(), v.end());
int s = v.size();
if (s >= 2) {
res = max(res, v[s-1]+v[s-2]+l);
}
if (s >= 3) {
res = max(res, v[s-2]+v[s-3]+2*l);
}
return res;
}
