#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define ii pair<int, int>
#define fi first
#define se second;
const int maxn = 1e5 + 5;
int n, m, l;
vector<ii> ke[maxn];
ll d[maxn];
int tplt;
int X[maxn], Y[maxn];
ll dis, C_node[maxn], l_path[maxn];
ll res;
int par[maxn];
void inp(){
cin >> n >> m >> l;
for(int i=0; i<m; i++){
int x, y, w; cin >> x >> y >> w;
ke[x].push_back({y, w});
ke[y].push_back({x, w});
}
}
void dfs(int u, int parent){
for(auto it : ke[u]){
int v = it.fi, w = it.se;
if(v != parent){
d[v] = d[u] + w;
if(d[v] > dis){
dis = d[v];
X[tplt] = v;
}
dfs(v, u);
}
}
}
void DFS(int u, int i){
for(auto it : ke[u]){
int v = it.fi, w = it.se;
if(v != par[u]){
par[v] = u;
d[v] = d[u] + w;
if(d[v] > l_path[i]){
l_path[i] = d[v];
Y[i] = v;
}
DFS(v, i);
}
}
}
void solve(){
for(int i=0; i<n; i++){
if(!d[i]){
dis = 0;
tplt++;
X[tplt] = i;
dfs(i, i);
}
}
memset(d, 0, sizeof(d));
for(int i=1; i<=tplt; i++){
if(!d[X[i]]){
Y[i] = X[i];
DFS(X[i], i);
}
}
// for(int i=1; i<=tplt; i++){
// cout << l_path[i] << "\n";
// }
// for(int i=1; i<=tplt; i++){
//// cout << C_node[i] << "\n";
// cout << X[i] << " " << Y[i] << "\n";
// }
// cout << l_path[3] << " " << Y[3] << " " << d[Y[3]] << endl;
memset(C_node, 70, sizeof(C_node));
for(int i=1; i<=tplt; i++){
C_node[i] = min(C_node[i], max(l_path[i] - d[Y[i]], d[Y[i]]));
while(X[i] != Y[i]){
C_node[i] = min(C_node[i], max(l_path[i] - d[Y[i]], d[Y[i]]));
Y[i] = par[Y[i]];
}
}
// for(int i=1; i<=tplt; i++){
// cout << C_node[i] << "\n";
//// cout << X[i] << " " << Y[i] << "\n";
// }
sort(C_node+1, C_node+tplt+1, greater<int>());
for(int i=1; i<=tplt; i++){
res = max(res, l_path[i]);
}
if(tplt >= 2){
res = max(res, C_node[1] + C_node[2] + l);
}
if(tplt >= 3){
res = max(res, C_node[2] + C_node[3] + 2*l);
}
cout << res << "\n";
}
int main(){
ios_base::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
inp();
solve();
return 0;
}
Compilation message
/usr/bin/ld: /tmp/ccfom7Do.o: in function `main':
dreaming.cpp:(.text.startup+0x0): multiple definition of `main'; /tmp/ccAnOH0r.o:grader.c:(.text.startup+0x0): first defined here
/usr/bin/ld: /tmp/ccAnOH0r.o: in function `main':
grader.c:(.text.startup+0xd1): undefined reference to `travelTime'
collect2: error: ld returned 1 exit status
