#include <bits/stdc++.h>
#include <iostream>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
typedef tree<ll,null_type,less_equal<ll>,rb_tree_tag,tree_order_statistics_node_update> order_set;
mt19937 mt_rand(chrono::high_resolution_clock::now().time_since_epoch().count());
//uniform_int_distribution<int> gen; ///(min, max)
//int random() {return gen(mt_rand);}
const int mxN=1e5+5;
const int mod=998244353;
const int mxlogN=40;
const int mxK=26;
const int inf=2e9;
const int K=600;
struct edge
{
int u,v,w;
int other(int i)
{
return i^u^v;
}
}es[mxN];
bool vis[mxN];
vector<int> cur;
multiset<int> ms[mxN];
vector<int> adj[mxN];
int down[mxN], up[mxN];
int get_max(int i)
{
if(ms[i].empty()) return 0;
return *ms[i].rbegin();
}
void dfs(int i, int p)
{
vis[i]=1;
cur.push_back(i);
for(int e:adj[i])
{
int j=es[e].other(i);
if(j==p) continue;
dfs(j,i);
ms[i].insert(down[j]+es[e].w);
}
down[i]=get_max(i);
}
void dfs2(int i, int p)
{
for(int e:adj[i])
{
int j=es[e].other(i);
if(j==p) continue;
ms[i].erase(ms[i].find(down[j]+es[e].w));
up[j]=es[e].w+max(get_max(i),up[i]);
ms[i].insert(down[j]+es[e].w);
dfs2(j,i);
}
}
int travelTime(int N,int M,int L,int A[],int B[],int T[])
{
int n=N, m=M;
for(int i=0; i<m; i++)
{
int u=A[i],v=B[i],w=T[i];
es[i]={u,v,w};
adj[u].push_back(i);
adj[v].push_back(i);
}
int ans=0;
vector<int> vs;
for(int i=0; i<n; i++)
{
if(!vis[i])
{
dfs(i,i);
dfs2(i,i);
int mx=0, mn=inf;
for(int i:cur)
{
mx=max(mx,max(down[i],up[i]));
mn=min(mn,max(down[i],up[i]));
}
ans=max(ans,mx);
vs.push_back(mn);
cur.clear();
}
}
sort(vs.begin(),vs.end());
int sz=vs.size();
if(sz<3)
{
if(sz==1) return ans;
return max(ans,vs[0]+vs[1]+L);
}
return max(ans,vs[sz-2]+vs[sz-3]+L+L);
}
/*
int main()
{
}*/
/*
7 3
4 1 3 4 0 2 3
*/
Compilation message
/usr/bin/ld: /tmp/ccOlXVvd.o: in function `main':
grader.c:(.text.startup+0xd1): undefined reference to `travelTime'
collect2: error: ld returned 1 exit status
