#include "dreaming.h"
#include<bits/stdc++.h>
using namespace std;
vector<vector<pair<int, int> > > adj;
vector<bool> visited;
vector<long long> res;
long long dfs(int u, int p){
long long ans = 0;
for(pair<int, int> x : adj[u]){
int v = x.first;
if(v != p){
ans = max(ans, dfs(v, u) + x.second);
}
}
return ans;
}
long long dfs2(int u, int p){
visited[u] = true;
long long ans = res[u];
for(pair<int, int> x : adj[u]){
int v = x.first;
if(v != p){
ans = min(ans, dfs2(v, u));
}
}
return ans;
}
int travelTime(int N, int M, int L, int A[], int B[], int T[]){
adj.resize(N);
visited.resize(N);
res.resize(N);
for(int i = 0; i < M; i++){
adj[A[i]].push_back(make_pair(B[i], T[i]));
adj[B[i]].push_back(make_pair(A[i], T[i]));
}
for(int i = 0; i < N; i++){
res[i] = dfs(i, 0);
}
vector<long long> thing;
for(int i = 0; i < N; i++){
if(!visited[i]){
thing.push_back(dfs2(i, 0));
}
}
sort(thing.begin(), thing.end());
reverse(thing.begin(), thing.end());
if((int)thing.size() > 1){
long long stuff1 = 0;
for(int i = 1; i < N; i++){
stuff1 = max(stuff1, thing[0] + thing[i] + L);
}
stuff1 = max(stuff1, thing[1] + thing[2] + 2 * L);
long long stuff2 = 0;
for(int i = 0; i < N; i++){
if(i == 1) continue;
stuff2 = max(stuff2, thing[1] + thing[i] + L);
}
stuff2 = max(stuff2, thing[0] + thing[2] + 2 * L);
return min(stuff1, stuff2);
}
else{
return 0;
}
}
// int main(){
// int n, m, l;
// cin >> n >> m >> l;
// int a[m];
// int b[m];
// int t[m];
// for(int i = 0; i < m; i++){
// cin >> a[i] >> b[i] >> t[i];
// }
// cout << travelTime(n, m, l, a, b, t) << "\n";
// }
