#include "dreaming.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
#define st first
#define nd second
#define pb push_back
#define all(a) a.begin(),a.end()
#define rep(a,b) for(int a = 0;a<b;a++)
const int inf = 1e9;
const ll infl = 1e18;
int d[100000];
int mxd[100000];
bool vis[100000];
vector<vector<pair<int,int>>> gr;
void cd(int v)
{
//cerr<<v<<"\n";
vis[v] = true;
for(pair<int,int> i : gr[v])
{
if(!vis[i.st])
{
cd(i.st);
mxd[v] = max(mxd[v], i.nd + mxd[i.st]);
}
}
}
int mx;
void dfs(int v,int md)
{
if(v == -1)
{
return;
}
vis[v] = true;
vector<pair<int,int>> vv;
for(pair<int,int> i : gr[v])
{
if(!vis[i.st])
{
vv.pb({mxd[i.st] + i.nd,i.st});
}
}
sort(all(vv));
reverse(all(vv));
vv.pb({0,-1});
mx = min(mx,max(md,vv[0].st));
for(int i = 1;i<gr[v].size();i++)
{
dfs(vv[i].nd,max(md,vv[0].st) + vv[i].st - mxd[vv[i].nd]);
}
if(vv[0].nd != -1) dfs(vv[0].nd,max(md,vv[1].st) + vv[0].st - mxd[vv[0].nd]);
}
int travelTime(int n,int m,int l,int a[],int b[],int t[])
{
gr.resize(n);
rep(i,m)
{
gr[a[i]].pb({b[i],t[i]});
gr[b[i]].pb({a[i],t[i]});
}
rep(i,n)
{
if(!vis[i])
{
cd(i);
}
}
vector<int> aa;
rep(i,n) vis[i] = false;
rep(i,n)
{
if(!vis[i])
{
mx = inf;
dfs(i,0);
aa.pb(mx);
}
}
sort(all(aa));
reverse(all(aa));
//rep(i,aa.size()) cerr<<aa[i]<<"\n";
if(aa.size() == 1)
{
return aa[0];
}
else if(aa.size() == 2)
{
return aa[0] + aa[1] + l;
}
else
{
return max(aa[0] + aa[1] + l, aa[1] + aa[2] + l * 2);
}
}
