#include "dreaming.h"
#include<bits/stdc++.h>
using namespace std;
vector<pair<int,int>> v[100010];
int visited[100010];
int dp[100010];
int sumi1[100010];
int node1[100010];
int sumi2[100010];
priority_queue<int> pq;
void dfs(int u,int pa){
for(auto g:v[u]){
if(g.first!=pa){
dfs(g.first,u);
if(g.second+sumi1[g.first]>sumi1[u]){
sumi2[u]=sumi1[u];
sumi1[u]=g.second+sumi1[g.first];
node1[u]=g.first;
}
else if(g.second+sumi1[g.first]>sumi2[u]){
sumi2[u]=g.second+sumi1[g.first];
}
}
}
visited[u]=1;
}
void dfs2(int u,int pa,int root,int q){
dp[root]=min(dp[root],max(q,sumi1[u]));
for(auto g:v[u]){
if(g.first!=pa){
if(g.first!=node1[u]){
dfs2(g.first,u,root,max(q,sumi1[u])+g.second);
}
else{
dfs2(g.first,u,root,max(q,sumi2[u])+g.second);
}
}
}
}
int travelTime(int n, int m, int l, int a[], int b[], int t[]) {
for(int i=0;i<m;i++){
v[a[i]].push_back({b[i],t[i]});
v[b[i]].push_back({a[i],t[i]});
}
int co=0;
for(int i=0;i<n;i++){
if(visited[i]==1)
continue;
co++;
dfs(i,-1);
dp[i]=INT_MAX;
dfs2(i,-1,i,0);
pq.push(dp[i]);
}
if(co==1)
return 0;
if(co==2){
int xxx=pq.top();
pq.pop();
int yyy=pq.top();
return(xxx+yyy+l);
}
int xxx=pq.top();
pq.pop();
int yyy=pq.top();
pq.pop();
int zzz=pq.top();
return(max(xxx+l+yyy,yyy+zzz+2*l));
}
