#include "dreaming.h"
#include <bits/stdc++.h>
using ll = int;
using namespace std;
typedef vector<ll> vi;
typedef vector<vi> vvi;
typedef pair<ll,ll> ii;
typedef vector<ii> vii;
typedef vector<vii> vvii;
const ll INF = 1e9;
#define S second
#define F first
class SmallTree{
private:
vvii adjList;
ll root,n,maxDist,diam;
vi heights;
map<ii,vi> unrootedTree;
// the key is the pair(node, parent of node)
// the value is the maxDist of that subtree
ll findMaxDist (ll curRt){
queue<ll> q;
vi dist;
dist.assign(n,INF);
dist[curRt] = 0;
q.push(curRt);
ll res = 0;
while (!q.empty()){
ll v = q.front();
q.pop();
for (auto e: adjList[v]){
if (dist[e.S] == INF){
dist[e.S] = dist[v]+e.F;
res = max(res,dist[e.S]);
q.push(e.S);
}
}
}
return res;
}
void findRoot(){
// slow step
maxDist = INF;
root = -1;
for (ll rt = 0; n > rt; rt++){
ll te = findMaxDistDP(rt,-1);
if (te < maxDist){
root = rt; maxDist = te;
}
}
}
ll findHeight (ll p, ll v){
heights[v] = 0;
for (auto e: adjList[v]){
if (e.S == p) continue;
heights[v] = max(heights[v],findHeight(v,e.S)+e.F);
}
return heights[v];
}
void findDiam (){
heights.resize(n);
findHeight(-1,root);
vi dists;
for (auto e: adjList[root]){
dists.push_back(e.F+heights[e.S]);
}
sort(dists.begin(),dists.end());
reverse(dists.begin(),dists.end());
diam = 0;
for (ll i = 0; 2 > i && dists.size() > i; i++){
diam += dists[i];
}
}
ll findMaxDistDP (ll v, ll p){
if (unrootedTree.find(ii(v,p)) != unrootedTree.end()){
return unrootedTree[ii(v,p)][0];
}else{
vi res; res.push_back(0);
for (auto e: adjList[v]){
if (e.S == p) continue;
res.push_back(findMaxDistDP(e.S,v)+e.F);
sort(res.begin(),res.end(), greater<ll>());
if (res.size() > 2) res.pop_back();
}
unrootedTree[ii(v,p)] = res;
return res[0];
}
}
public:
SmallTree(const vvii& _adjList): adjList(_adjList){
n = adjList.size();
findRoot();
findDiam();
}
ll getMaxDist(){
return maxDist;
}
ll getDiam(){
return diam;
}
SmallTree(){}
};
class UnionFind{
private:
ll n;
vi sz, p;
public:
UnionFind(ll n): n(n), sz(n,1), p(n){
for (ll i = 0; n > i; i++) p[i] = i;
}
ll root(ll x){
if (p[x] != x) p[x] = root(p[x]);
return p[x];
}
void unify (ll x, ll y){
//cout <<"unify: " << x << " " << y << endl;
x = root(x), y = root(y);
if (x == y) return;
if (sz[x] > sz[y]) swap(x,y);
p[x] = y;
sz[y] += sz[x];
}
vvi get_ccs(){
vvi te;
te.resize(n);
for (ll i = 0; n > i; i++){
te[root(i)].push_back(i);
}
vvi res;
for (ll i = 0; n > i; i++){
if (te[i].size() > 0) res.push_back(te[i]);
}
return res;
}
};
int travelTime(int n, int m, int l, int a[], int b[], int t[]) {
UnionFind uf(n);
for (ll i = 0; m > i; i++){
uf.unify(a[i], b[i]);
}
vvi ccs = uf.get_ccs();
vii encoding(n);
for (ll i = 0; ccs.size() > i; i++){
for (ll j = 0; ccs[i].size() > j ;j++){
encoding[ccs[i][j]] = ii(i,j);
}
}
vector<vvii> adjLists;
adjLists.resize(ccs.size());
for (ll i = 0; ccs.size() > i; i++){
adjLists[i].resize(ccs[i].size());
}
for (ll i = 0; m > i; i++){
ii code = encoding[a[i]];
adjLists[code.F][code.S].emplace_back(t[i],encoding[b[i]].S);
code = encoding[b[i]];
adjLists[code.F][code.S].emplace_back(t[i],encoding[a[i]].S);
}
/*
for (auto i: ccs){
cout << "cc: \n";
for (auto j: i){
cout << j << ' ';
}
cout << endl;
}
for (auto i: adjLists){
cout << "adjList: \n";
for (ll j = 0; i.size() > j; j++){
cout << j << ": ";
for (auto p: i[j]) cout << "(" << p.F << " , " << p.S << "), ";
cout << endl;
}
}
*/
vector<SmallTree> smallTrees;
smallTrees.resize(adjLists.size());
for (ll i = 0; adjLists.size() > i; i++){
smallTrees[i] = SmallTree(adjLists[i]);
}
/*
cout << "maxDists: ";
for (auto i: smallTrees){
cout << i.getMaxDist() << ' ';
}
cout << endl;
cout << "diams: ";
for (auto i: smallTrees){
cout << i.getDiam() << ' ';
}
cout << endl;
*/
ll res = 0;
for (auto i: smallTrees){
res = max(res,i.getDiam());
}
vi maxDists; maxDists.resize(smallTrees.size());
for (ll i = 0; smallTrees.size() > i; i++){
maxDists[i] = smallTrees[i].getMaxDist();
}
sort(maxDists.begin(),maxDists.end());
reverse(maxDists.begin(),maxDists.end());
if (maxDists.size() >= 2){
ll te = l;
for (ll i = 0; 2 > i && maxDists.size() > i; i++){
te += maxDists[i];
}
res = max(te,res);
}
if (maxDists.size() >= 3){
ll te = 2*l;
for (ll i = 1; 3 > i && maxDists.size() > i; i++)
te += maxDists[i];
res = max(te,res);
}
return res;
}
/*
#define fail(s, x...) do { \
fprintf(stderr, s "\n", ## x); \
exit(1); \
} while(0)
#define MAX_N 100000
static int A[MAX_N];
static int B[MAX_N];
static int T[MAX_N];
int main() {
int N, M, L, i;
int res;
FILE *f = fopen("dreaming.in", "r");
if (!f)
fail("Failed to open input file.");
res = fscanf(f, "%d%d%d", &N, &M, &L);
for (i = 0; i < M; i++)
res = fscanf(f, "%d%d%d", &A[i], &B[i], &T[i]);
fclose(f);
int answer = travelTime(N, M, L, A, B, T);
printf("%d\n", answer);
return 0;
}
*/
