#include "dreaming.h"
/*
ID: awesome35
LANG: C++14
TASK: vans
*/
#define _CRT_SECURE_NO_WARNINGS
#include<bits/stdc++.h>
#include<unordered_set>
#include<unordered_map>
#include<chrono>
using namespace std;
typedef pair<int, int> pii;
typedef long long ll;
typedef pair<ll, ll> pll;
typedef long double ld;
typedef vector<int> vi;
typedef vector<ll> vll;
typedef vector<pair<int, int>> vpi;
typedef vector<pair<ll, ll>> vpll;
#define FOR(i,a,b) for (int i = (a); i < (b); ++i)
#define F0R(i,a) FOR(i,0,a)
#define ROF(i,a,b) for (int i = (b)-1; i >= (a); --i)
#define R0F(i,a) ROF(i,0,a)
#define trav(a,x) for (auto& a: x)
#define pb push_back
#define mp make_pair
#define rsz resize
#define sz(x) int(x.size())
#define all(x) x.begin(),x.end()
#define f first
#define s second
#define cont continue
#define endl '\n'
#define ednl '\n'
#define test int testc;cin>>testc;while(testc--)
#define pr(a, b) trav(x,a)cerr << x << b; cerr << endl;
#define message cout << "My name's Ozymandias, king of kings: look on my works, ye mighty and despair!" <<endl;
const int dx[4] = { 1,0,-1,0 }, dy[4] = { 0,1,0,-1 }; // for every grid problem!!
const ll linf = 4000000000000000000LL;
const ll inf = 1000000007;//998244353
const ld pi = 3.1415926535;
void pv(vi a) { trav(x, a)cout << x << " "; cout << endl; }void pv(vll a) { trav(x, a)cout << x << " "; cout << endl; }void pv(vector<vi>a) {
F0R(i, sz(a)) { cout << i << endl; pv(a[i]); cout << endl; }
}void pv(vector<vll>a) { F0R(i, sz(a)) { cout << i << endl; pv(a[i]); }cout << endl; }void pv(vector<string>a) { trav(x, a)cout << x << endl; cout << endl; }
int n, m, l, maxdia;
vector<vpi>adj;
vi depth, parents, type;
int cur;
void depth_(int i, int p)
{
parents[i] = p;
depth[i] = 0, type[i] = cur;
trav(x, adj[i])
{
if (x.f != p)
{
depth_(x.f, i);
depth[i] = max(depth[i], depth[x.f] + x.s);
}
}
}
vi up;
void up_(int i, int p)
{
up[i] = max(0, up[i]);
multiset<int, greater<int>>t = { up[i] };
trav(x, adj[i])
{
if (x.f != p)
{
t.insert(x.s + depth[x.f]);
}
}
trav(x, adj[i])
{
if (x.f != p)
{
t.erase(t.find(x.s + depth[x.f]));
up[x.f] = x.s + *t.begin();
t.insert(x.s + depth[x.f]);
}
}
trav(x, adj[i])
{
if (x.f != p)
{
up_(x.f, i);
}
}
}
int travelTime(int a, int b, int c, int* d, int* e, int* f)
{
n = a;
m = b;
l = c;
adj.rsz(n);
F0R(i, m)
{
adj[d[i]].pb({ e[i],f[i] });
adj[e[i]].pb({ d[i],f[i] });
}/*
if (n == 1)
{
return 0;
}
if (n == 2)
{
return m == 1 ? adj[0][0].s : l;
}*/
depth.rsz(n, -1);
parents.rsz(n);
type.rsz(n);
F0R(i, n)
{
if (depth[i] == -1)depth_(i, -1), cur++;
}
up.rsz(n, -1);
F0R(i, n)
{
if (up[i] == -1)up_(i, -1);
}
F0R(i, n)
{
maxdia = max(maxdia, up[i] + depth[i]);
}
vi size(cur, inf);
F0R(i, n)
{
multiset<int>t;
trav(x, adj[i])
{
if (x.f != parents[i])
{
t.insert(x.s + depth[x.f]);
}
}
t.insert(up[i]);
if (sz(t) == 1)continue;
size[type[i]] = min(size[type[i]], *t.rbegin());
}
trav(x, size)if (x == inf)x = 0;
sort(all(size), greater<int>());
return max({ maxdia,sz(size) > 1 ? size[0] + size[1] + l : 0, sz(size) > 2 ? size[1] + size[2] + 2 * l : 0 });
}
