#include"dreaming.h"
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#include <bits/stdc++.h>
#define fi first
#define se second
#define pb push_back
#define sz(a) (int)a.size()
#define all(a) a.begin(), a.end()
#define rall(a) a.rbegin(), a.rend()
#define ff(i,a,b) for(int i=a;i<=b;i++)
#define fb(i,b,a) for(int i=b;i>=a;i--)
using namespace std;
using namespace __gnu_pbds;
typedef long long ll;
typedef pair<int,int> pii;
const int maxn = 100005;
const int inf = 1e9 + 5;
template<typename T>
using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
// os.order_of_key(k) the number of elements in the os less than k
// *os.find_by_order(k) print the k-th smallest number in os(0-based)
int n, m, L;
vector<pii> g[maxn];
int pref[maxn];
int br = 0;
int d[maxn];
pii last[maxn];
int used[maxn];
int was[maxn];
int bfs(int s){
queue<int> q;
q.push(s);
used[s] = br;
while(!q.empty()){
int v = q.front(); q.pop();
for(auto c : g[v]){
int u = c.fi;
int w = c.se;
if(!used[u]){
used[u] = br;
d[u] = d[v] + w;
q.push(u);
}
}
}
int a = 0;
int mx = 0;
ff(i,1,n){
if(used[i] != br)continue;
if(d[i] > mx){
mx = d[i];
a = i;
}
}
was[a] = br;
d[a] = 0;
q.push(a);
while(!q.empty()){
int v = q.front(); q.pop();
for(auto c : g[v]){
int u = c.fi;
int w = c.se;
if(!was[u]){
was[u] = br;
d[u] = d[v] + w;
last[u] = {v, w};
q.push(u);
}
}
}
int dia = 0;
int b = 0;
ff(i,1,n){
if(was[i] != br)continue;
if(d[i] > dia){
dia = d[i];
b = i;
}
}
int x = b;
vector<pii> put;
while(x != a){
pii z = last[x];
put.pb(z);
x = z.fi;
}
put.pb({b, 0});
ff(i,0,sz(put) - 1){
if(i == 0)pref[i] = put[i].se;
else pref[i] = pref[i - 1] + put[i].se;
}
// for(auto c : put)cout << c.fi << " " << c.se << endl;
// ff(i,0,sz(put) - 1)cout << pref[i] << " ";
// cout << endl;
int rez = inf;
int ko = 0;
ff(i,0,sz(put) - 1){
int mx = max(pref[i], pref[sz(put) - 1] - pref[i]);
if(mx < rez){
rez = mx;
ko = put[i].fi;
}
}
if(ko == 0)ko = s;
return ko;
}
int dia = 0;
int dfs(int v, int p, int duz){
int best = duz;
for(auto c : g[v]){
int u = c.fi;
int w = c.se;
if(u != p){
int dist = dfs(u, v, duz + w);
dia = max(dia, best + dist - 2 * duz);
best = max(best, dist);
}
}
return best;
}
int travelTime(int N, int M, int L1, int A[], int B[], int T[]){
n = N;
m = M;
L = L1;
ff(i,0,m - 1){
int u = A[i] + 1;
int v = B[i] + 1;
int w = T[i];
g[u].pb({v, w});
g[v].pb({u, w});
}
vector<int> vec;
ff(i,1,n){
if(!used[i]){
br += 1;
int x = bfs(i);
vec.pb(x);
}
}
ff(i,1,sz(vec) - 1){
g[vec[0]].pb({vec[i], L});
g[vec[i]].pb({vec[0], L});
}
dfs(1, -1, 0);
return dia;
}
//int main()
//{
// ios::sync_with_stdio(false);
// cout.tie(nullptr);
// cin.tie(nullptr);
// cin >> n >> m >> L;
// ff(i,1,m){
// int u, v, w;
// cin >> u >> v >> w;
// g[u].pb({v, w});
// g[v].pb({u, w});
// }
// return 0;
//}
/**
12 8 2
1 9 4
9 3 2
3 8 4
12 6 3
6 2 7
10 2 5
2 4 1
7 11 3
// probati bojenje sahovski ili slicno
**/
