/*DavitMarg*/
#include <iostream>
#include <algorithm>
#include <cmath>
#include <vector>
#include <string>
#include <cstring>
#include <map>
#include <unordered_map>
#include <set>
#include <queue>
#include <iomanip>
#include <bitset>
#include <stack>
#include <cassert>
#include <iterator>
#include <fstream>
#define mod 1000000000ll
#define LL long long
#define LD long double
#define MP make_pair
#define PB push_back
#define all(v) v.begin(), v.end()
using namespace std;
const int N = 100005;
#ifndef death
//#include "dreaming.h"
#endif
int n, used[N], color;
LL x, ans[N], mx[N];
vector<pair<int, LL>> g[N];
vector<LL> dp[N];
void dfs(int v, int p = -1)
{
used[v] = color;
dp[v].PB(0);
dp[v].PB(0);
for (int i = 0; i < g[v].size(); i++)
{
int to = g[v][i].first;
LL d = g[v][i].second;
assert((bool)used[to] == (to == p));
if (to == p)
continue;
dfs(to, v);
dp[v].PB(dp[to][0] + d);
mx[v] = max(mx[v], mx[to]);
}
sort(all(dp[v]));
reverse(all(dp[v]));
mx[v] = dp[v][0] + dp[v][1];
}
void dfs2(int v, int p, LL dist)
{
vector<LL> d;
d.PB(dp[v][0]);
d.PB(dp[v][1]);
d.PB(dist);
sort(all(d));
reverse(all(d));
ans[v] = d[0];
for (int i = 0; i < g[v].size(); i++)
{
int to = g[v][i].first;
LL d = g[v][i].second;
if (to == p)
continue;
LL newdist = dist;
if (dp[to][0] + d == dp[v][0])
newdist = max(newdist, dp[v][1]);
else
newdist = max(newdist, dp[v][0]);
newdist += d;
dfs2(to, v, newdist);
ans[v] = min(ans[v], ans[to]);
}
}
int travelTime(int N, int M, int L, int A[], int B[], int T[])
{
LL ANS = 0;
n = N;
x = L;
while (M--)
{
g[A[M]].PB(MP(B[M], T[M]));
g[B[M]].PB(MP(A[M], T[M]));
}
vector<LL> res;
for (int i = 0; i < n; i++)
{
if (used[i])
continue;
color++;
dfs(i);
ANS = max(ANS, mx[i]);
dfs2(i, -1, 0);
//cout << ans[i] << " !\n";
res.PB(ans[i]);
}
sort(all(res));
reverse(all(res));
if (res.size() > 1)
{
ANS = max(x + res[0] + res[1], ANS);
if (res.size() > 2)
ANS = max(ANS, res[1] + res[2] + x + x);
}
return ANS;
}
#ifdef death
int main()
{
int N, M, L, A[102], B[102], D[102];
cin >> N >> M >> L;
for (int i = 0; i < M; i++)
cin >> A[i] >> B[i] >> D[i];
cout << travelTime(N, M, L, A, B, D) << endl;
return 0;
}
#endif
/*
7 5 1
0 1 5
1 2 3
2 3 2
1 4 4
4 5 2
8 6 100
0 1 10
1 2 15
2 7 11
3 4 3
4 5 332
5 6 3
12 8 2
0 8 4
8 2 2
2 7 4
5 11 3
5 1 7
1 3 1
1 9 5
10 6 3
*/
Compilation message
dreaming.cpp: In function 'void dfs(int, int)':
dreaming.cpp:42:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (int i = 0; i < g[v].size(); i++)
~~^~~~~~~~~~~~~
dreaming.cpp: In function 'void dfs2(int, int, long long int)':
dreaming.cpp:68:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (int i = 0; i < g[v].size(); i++)
~~^~~~~~~~~~~~~
/tmp/ccnh90rB.o: In function `main':
grader.c:(.text.startup+0xa2): undefined reference to `travelTime'
collect2: error: ld returned 1 exit status
