#include <stdio.h>
#include <vector>
#include <queue>
#include <algorithm>
using namespace std;
int N,M,L;
int a[100002];
int d[100002],q[100002];
int dia[100002],tmp;
int path[100002];
bool check[100002];
vector<pair<int,int> > edge[100002];
int bfs(int x){
int i,r;
int v,nextv,big;
int top,rear,ansv;
top = 0;
rear = 1;
q[1] = x;
d[x] = 0;
while(true){
top++;
if(top > rear) break;
for(i=0; i<edge[q[top]].size(); i++){
v = edge[q[top]][i].first;
if(d[v] > d[q[top]]+edge[q[top]][i].second){
d[v] = d[q[top]]+edge[q[top]][i].second;
rear++;
q[rear] = v;
}
}
}
big = -1;
for(i=1; i<=rear; i++){
if(big < d[q[i]]){ big = d[q[i]]; v = q[i]; }
}
check[v] = true;
d[v] = 0;
top = 0;
rear = 1;
q[1] = v;
while(true){
top++;
if(top > rear) break;
for(i=0; i<edge[q[top]].size(); i++){
nextv = edge[q[top]][i].first;
if(!check[nextv]){
check[nextv] = true;
d[nextv] = d[q[top]] + edge[q[top]][i].second;
rear++;
q[rear] = nextv;
path[nextv] = q[top];
}
}
}
big = -1;
for(i=1; i<=rear; i++){
if(big < d[q[i]]){ big = d[q[i]]; nextv = q[i]; }
}
tmp = big;
r = 999999999;
x = nextv;
while(true){
if(r > max(d[x],d[nextv]-d[x])){ r = max(d[x],d[nextv]-d[x]); ansv = x; }
if(v == x) break;
x = path[x];
}
/*for(i=1; i<=rear; i++) d[q[i]] = 999999999;
d[ansv] = 0;
top = 0; rear = 1; q[1] = ansv;
while(true){
top++; if(top > rear) break;
for(i=0; i<edge[q[top]].size(); i++){
if(d[edge[q[top]][i].first] == 999999999){
d[edge[q[top]][i].first] = d[q[top]] + edge[q[top]][i].second;
rear++; q[rear] = edge[q[top]][i].first; }
}
}
big = -1;
for(i=1; i<=rear; i++) if(big < d[q[i]]) big = d[q[i]];
if(r != big) printf("%d %d\n",r,big);*/
return r;
}
#include "dreaming.h"
int travelTime(int n, int m, int l, int A[], int B[], int T[]) {
int i;
int x,y,cost;
int rear;
//freopen("input.txt","r",stdin);
//scanf("%d %d %d",&N,&M,&L);
N = n; M = m; L = l;
for(i=1; i<=N; i++) d[i] = 999999999;
for(i=1; i<=M; i++){
//scanf("%d %d %d",&x,&y,&cost);
x = A[i-1]; y = B[i-1]; cost = T[i-1];
x++; y++;
edge[x].push_back(make_pair(y,cost));
edge[y].push_back(make_pair(x,cost));
}
rear = 0;
for(i=1; i<=N; i++){
if(check[i]) continue;
x = bfs(i);
rear++;
a[rear] = x;
dia[rear] = tmp;
//printf("%d\n",x);
}
sort(a+1,a+rear+1);
sort(dia+1,dia+rear+1);
if(rear == 1){
return dia[1];
printf("%d",dia[1]);
}else if(rear == 2){
return max(a[1]+a[2]+L,dia[2]);
printf("%d",max(a[1]+a[2]+L,dia[2]));
}else{
return max(max(a[rear]+a[rear-1]+L,a[rear-1]+a[rear-2]+L+L),dia[rear]);
printf("%d",max(max(a[rear]+a[rear-1]+L,a[rear-1]+a[rear-2]+L+L),dia[rear]));
}
return 0;
}
