#include "bits/stdc++.h"
// #include "dreaming.h"
using namespace std;
const int maxn=1e5+5;
int idx,jog,ans;
int dp[maxn][2];
bool vis[maxn];
vector<pair<int,int>>E[maxn];
void calc(int nd,int pr){
vis[nd] = 1;
int a = 0,b = 0;
for(auto i : E[nd]){
if(i.first == pr) continue;
calc(i.first,nd);
if(dp[i.first][0] + i.second > a) b=a,a = dp[i.first][0] + i.second;
else if(dp[i.first][0] + i.second > b) b=dp[i.first][0] + i.second;
}
dp[nd][0] = a;
dp[nd][1] = b;
ans = max(ans,a + b);
}
void dfs(int nd,int pr,int yok){
vis[nd] = 1;
if(max(yok,dp[nd][0]) < jog){
idx = nd;
jog = max(yok,dp[nd][0]);
}
for(auto i : E[nd]){
if(i.first == pr) continue;
if(dp[i.first][0] + i.second == dp[nd][0]) dfs(i.first,nd,max(yok,dp[nd][1])+i.second);
else dfs(i.first,nd,max(yok,dp[nd][0])+i.second);
}
}
int travelTime(int N, int M, int L, int A[], int B[], int T[]) {
for(int i = 0;i < M;i++){
E[A[i]].push_back({B[i],T[i]});
E[B[i]].push_back({A[i],T[i]});
}
for(int i = 0;i < N;i++) if(!vis[i]) calc(i,0);
memset(vis,0,sizeof(vis));
vector<pair<int,int>>v;
for(int i = 0;i < N;i++){
if(vis[i]) continue;
idx = -1;
jog = 2e9;
dfs(i,-1,0);
v.push_back({jog,idx});
}
sort(v.begin(),v.end());
reverse(v.begin(),v.end());
if(M != N-1) ans = max({ans,v[0].first + v[1].first + L});
if((int)v.size() >= 3) ans = max(ans,v[1].first+v[2].first + 2*L);
return ans;
}
int main(){
int n,m,l; cin >> n >> m >> l;
int a[m],b[m],t[m];
for(int i = 0;i < m;i++) cin >> a[i] >> b[i] >> t[i];
cout<<travelTime(n,m,l,a,b,t);
}
Compilation message
/usr/bin/ld: /tmp/ccWXP80q.o: in function `main':
dreaming.cpp:(.text.startup+0x0): multiple definition of `main'; /tmp/ccrvXDzr.o:grader.c:(.text.startup+0x0): first defined here
/usr/bin/ld: /tmp/ccrvXDzr.o: in function `main':
grader.c:(.text.startup+0xd1): undefined reference to `travelTime'
collect2: error: ld returned 1 exit status
