#include "dreaming.h"
#include<bits/stdc++.h>
using namespace std;
vector<vector<pair<int,int> >> adj;
vector<bool> vis;
vector<vector<int> > t;
vector<int> d,ty;
int n,m,l;
void dfs(int node,int f)
{
vis[node]=true;
int k=adj[node].size();
for(int x=0;x<k;x++)
{
int to=adj[node][x].first;
if(!vis[to])
{
t[f].push_back(to);
dfs(to,f);
}
}
}
void dfs3(int node,int dis[])
{
vis[node]=true;
int k=adj[node].size();
for(int x=0;x<k;x++)
{
int to=adj[node][x].first;
if(!vis[to])
{
dis[to]=dis[node]+adj[node][x].second;
dfs3(to,dis);
}
}
}
int get(int y)
{
int cn=t[y].size();
int dis[n+1]={0},disa[n+1]={0},disb[n+1]={0},a=0,b=0,cur=0;
vis.assign(n+1,false);
if(adj[y].size()!=0)
dfs3(y,dis);
else
return 0;
for(int x=0;x<cn;x++)
{
if(cur<=dis[t[y][x]] && t[y][x]!=y)
{
a=t[y][x];
cur=dis[t[y][x]];
}
}
vis.assign(n+1,false);
dfs3(a,disa);
cur=0;
for(int x=0;x<cn;x++)
{
if(cur<disa[t[y][x]] && t[y][x]!=a)
{
b=t[y][x];
cur=disa[t[y][x]];
}
}
vis.assign(n+1,false);
dfs3(b,disb);
int ans=disb[a];
for(int x=0;x<cn;x++)
ans=min(ans,max(disa[t[y][x]],disb[t[y][x]]));
d.push_back(disa[b]);
return ans;
}
int travelTime(int ne,int me,int le,int u[],int v[],int te[])
{
n=ne;m=me;l=le;
adj.resize(n+1);
t.resize(n+1);
vis.assign(n+1,false);
for(int x=0;x<m;x++)
{
adj[u[x]+1].push_back(make_pair(v[x]+1,te[x]));
adj[v[x]+1].push_back(make_pair(u[x]+1,te[x]));
}
int c=0;
for(int x=1;x<=n;x++)
{
if(!vis[x])
{
t[x].push_back(x);
dfs(x,x);
ty.push_back(x);
}
}
int z=ty.size();
int dia[z]={0};
for(int x=0;x<z;x++)
dia[x]=get(ty[x]);
int ans=0,ans1=0;
/*for(int x=0;x<z;x++)
cout<<t[x]<<" "<<dia[x]<<endl;*/
for(int x=0;x<d.size();x++)
ans=max(ans,d[x]);
sort(dia,dia+z);
if(z-2>=0)
ans1=dia[z-1]+dia[z-2]+l;
if(z-3>=0)
ans1=max(ans1,dia[z-3]+dia[z-2]+2*l);
return max(ans1,ans);
}
/*int main()
{
int ne,me,le;
cin>>ne>>me>>le;
int te[me],ae[me],be[me];
for(int x=0;x<me;x++)
cin>>ae[x]>>be[x]>>te[x];
//for(int x=0;x<me;x++)
//ae[x]++,be[x]++;
cout<<travelTime(ne, me, le, ae , be , te );
}*/
