#pragma optimize("Bismillahirrahmanirrahim")
//█▀█─█──█──█▀█─█─█
//█▄█─█──█──█▄█─█■█
//█─█─█▄─█▄─█─█─█─█
//Allahuekber
//ahmet23 orz...
//FatihSultanMehmedHan
//YavuzSultanSelimHan
//AbdulhamidHan
//Sani buyuk Osman Pasa Plevneden cikmam diyor.
#define author tolbi
#include<bits/stdc++.h>
using namespace std;
#define endl '\n'
#define sortarr(x) sort(x.begin(), x.end())
#define sortrarr(x) sort(x.rbegin(), x.rend())
#define coutarr(x) for (auto &it : x) cout<<it<<" ";cout<<endl;
#define rev(x) reverse(x.begin(), x.end())
#define tol(bi) (1LL<<((int)(bi)))
mt19937 ayahya(chrono::high_resolution_clock().now().time_since_epoch().count());
typedef long long ll;
const ll MOD = 1e9+7;
const ll INF = 1e18;
#include "dreaming.h"
int travelTime(int n, int m, int l, int a[], int b[], int t[]) {
vector<vector<pair<int,int>>> arr(n);
for (int i = 0; i < m; i++){
arr[a[i]].push_back({b[i],t[i]});
arr[b[i]].push_back({a[i],t[i]});
}
vector<int> adp(n,-1);
vector<int> bdp(n,-1);
vector<bool> vis(n,false);
int an,bn;
vector<int> x;
int ans = 0;
queue<pair<pair<int,int>,int>> q;
for (int src = 0; src < n; src++){
if (vis[src]) continue;
q.push({{src,-1},0});
vector<int> gez;
bn=src;
while (q.size()){
int node = q.front().first.first;
int lnode = q.front().first.second;
int w = q.front().second;
bdp[node]=w;
vis[node]=true;
gez.push_back(node);
q.pop();
for (int i = 0; i < arr[node].size(); i++){
if (arr[node][i].first==lnode) continue;
q.push({{arr[node][i].first,node},w+arr[node][i].second});
}
}
an=src;
for (int i = 0; i < gez.size(); i++){
if (bdp[gez[i]]>bdp[an]) an = gez[i];
}
q.push({{an,-1},0});
while (q.size()){
int node = q.front().first.first;
int lnode = q.front().first.second;
int w = q.front().second;
adp[node]=w;
q.pop();
for (int i = 0; i < arr[node].size(); i++){
if (arr[node][i].first==lnode) continue;
q.push({{arr[node][i].first,node},w+arr[node][i].second});
}
}
bn=src;
for (int i = 0; i < gez.size(); i++){
if (adp[gez[i]]>adp[bn]) bn = gez[i];
}
q.push({{bn,-1},0});
while (q.size()){
int node = q.front().first.first;
int lnode = q.front().first.second;
int w = q.front().second;
bdp[node]=w;
q.pop();
for (int i = 0; i < arr[node].size(); i++){
if (arr[node][i].first==lnode) continue;
q.push({{arr[node][i].first,node},w+arr[node][i].second});
}
}
ans=max(ans,adp[bn]);
int kk = adp[bn];
for (int i = 0; i < gez.size(); i++){
kk=min(kk,max(adp[gez[i]],bdp[gez[i]]));
}
x.push_back(kk);
}
sortrarr(x);
if (x.size()>=2) ans=max(ans,x[0]+x[1]+l);
if (x.size()>=3) ans=max(ans,x[1]+x[2]+l*2);
return ans;
}
