#include <iostream>
#include <vector>
#include "dreaming.h"
using namespace std;
int far;
int mx;
int mx2;
int mxd;
int mn;
int vis[100005];
int l1,l2,l3;
struct edge{
int nod;
int dis;
};
vector<edge> adj[100005];
int f(int dm, int che){
return max(che, dm-che);
}
void dfs1(int no, int di){
vis[no]=1;
if(di>=mx){
mx=di;
far = no;
}
for(auto x : adj[no]){
int n1 = x.nod;
int n2 = x.dis;
if(vis[n1]==0){
dfs1(n1, di+n2);
}
}
}
void dfs2(int no, int pa, int ra, int di, int dim){
if(di==mx){mn = min(mn, ra);}
for(auto x : adj[no]){
int n1 = x.nod;
int n2 = x.dis;
if(n1!=pa){
dfs2(n1, no, min(ra, f(dim, di+n2)), di+n2, dim);
}
}
}
int travelTime(int n, int m, int l, int a[], int b[],int t[]){
for(int i=0; i<=n; i++){
vis[i]=0;
}
l1=0;
l2=0;
l3=0;
mxd=0;
for(int i=1; i<=m; i++){
adj[a[i-1]].push_back({b[i-1], t[i-1]});
adj[b[i-1]].push_back({a[i-1], t[i-1]});
}
for(int i=0; i<n; i++){
if(vis[i]==0){
mx=0;
mx2=0;
mn = 1e9;
dfs1(i, 0);
int end = far;
dfs1(end, 0);
mxd = max(mx, mxd);
dfs2(far, 0, mx, 0, mx);
if(mn>l1){l1=mn;}
if(l1>l2){swap(l1, l2);}
if(l2>l3){swap(l2, l3);}
}
}
if(m==n-1){return max(mxd, l3);}
if(m==n-2){return max(l3+l2+l, mxd);}
else {
if(mxd>l3+l2+l&&mxd>l2+l1+l*2){return mxd;}
else {
return max(l3+l2+l, l2+l1+l*2);
}
}
}
