#include <bits/stdc++.h>
#include"dreaming.h"
#define rep(i, a, b) for (int i = (a); i < (b); i++)
#define per(i, a, b) for(int i = (a); i > (b); i--)
#define ll long long
#define pb push_back
#define xx first
#define yy second
#define pb push_back
#define pii pair<int,int>
#define vi vector<int>
#define vpii vector<pii>
using namespace std;
constexpr bool DEG = 0;
#define DEBUG if(DEG)
constexpr int N = 15+7;
vpii graf[N];
pii sred[N];
int par[N], odl[N],drugi, R, n,m,l;
int Find(int v){
if(par[v] == v) return v;
return par[v] = Find(par[v]);
}
pii f(pii a, pii b){
int sa = a.xx + a.yy;
int sb = b.xx + b.yy;
if(sa < sb) return a;
if(sa > sb) return b;
if(a.xx < b.xx) return a;
return b;
}
pii f2(pii a, pii b){
int sa = a.xx + a.yy;
int sb = b.xx + b.yy;
if(sa > sb) return a;
if(sa < sb) return b;
if(a.xx < b.xx) return a;
return b;
}
void Union(int a, int b){
a = Find(a); b = Find(b);
if(a == b) return;
par[b] = a;
pii w1 = {sred[a].xx + l, sred[b].xx}; if(w1.xx < w1.yy) swap(w1.xx, w1.yy);
pii w2 = {sred[a].xx, sred[b].xx + l}; if(w2.xx < w2.yy) swap(w2.xx, w2.yy);
pii w = f(w1, w2);
pii s = f2(sred[a], sred[b]);
int sw = w.xx + w.yy;
int ss = s.xx + s.yy;
if(ss > sw) sred[a] = s;
else if(ss == sw){
if(s.xx < w.xx) sred[a] = s;
else sred[a] = w;
}
else sred[a] = w;
}
int dfs(int v, int p){
int maxx = v;
for(auto i : graf[v]){
if(i.yy == p) continue;
odl[i.yy] = odl[v] + i.xx;
int c = dfs(i.yy, v);
if(odl[maxx] < odl[c]){
maxx = c;
}
Union(v,i.yy);
}
return maxx;
}
int countsred(int v, int p){
int czy = (v == drugi);
for(auto i : graf[v]){
if(i.yy == p) continue;
czy |= countsred(i.yy, v);
}
if(czy == 0) return 0;
pii xd = {odl[drugi] - odl[v], odl[v]};
if(xd.xx < xd.yy)
swap(xd.xx, xd.yy);
if(xd.xx < sred[R].xx)
sred[R] = xd;
return 1;
}
// int travelTime(int N,int M,int L, vi A, vi B, vi T){
int travelTime(int N,int M,int L, int A[], int B[], int T[]){
n = N; m = M; l = L;
rep(i,0,m){
graf[A[i]+1].pb({T[i], B[i]+1});
graf[B[i]+1].pb({T[i], A[i]+1});
}
rep(v,1,n+1) par[v] = v, odl[v] = -1;
rep(i,1,n+1){
if(odl[i] == -1){
odl[i] = 0; int c = dfs(i, 0);
odl[c] = 0; drugi = dfs(c, 0);
R = Find(i);
sred[R] = {odl[drugi], 0};
countsred(c, 0);
}
}
rep(i,1,n)
Union(i,i+1);
int w = Find(1);
int wynik = sred[w].xx + sred[w].yy;
return wynik;
}
/*
int main(){
int n1,m1,l1; cin>>n1>>m1>>l1;
vi a,b,c;
rep(i,0,m1){
int x,y,z; cin>>x>>y>>z;
a.pb(x);
b.pb(y);
c.pb(z);
}
cout<<travelTime(n1,m1,l1,a,b,c)<<"\n";
}
/*
12 8 2
0 1 4
1 2 2
2 3 4
5 6 3
6 7 7
7 8 5
9 10 3
11 7 1
5 2 100
0 1 8
3 4 4
*/
