#include "dreaming.h"
#include <bits/stdc++.h>

using namespace std;

vector<int> gozd[100005];
vector<int> teza[100005];
bool obiskan[100005];

pair<int,int> razdalja(int poz, int stars){//najde najbolj oddaljeno vozlisce
    pair<int,int> naj = make_pair(0,poz);
    for(int i=0;i<gozd[poz].size();i++){
        if(gozd[poz][i]==stars)continue;
        pair<int,int> curr = razdalja(gozd[poz][i],poz);
        curr.first+=teza[poz][i];
        if (curr.first>naj.first)naj = curr;
    }
    return naj;
}

int polmer(int poz, int stars, int cilj, int premer, int razdalja){
    int naj = max(razdalja,premer-razdalja);
    bool na_poti = (poz == cilj);
    obiskan[poz]=1;
    for(int i=0;i<gozd[poz].size();i++){
        if (gozd[poz][i]==stars)continue;
        int curr = polmer(gozd[poz][i],poz,cilj,premer,razdalja+teza[poz][i]);
        if(curr==-1)continue;
        na_poti=1;
        naj = min(naj,curr);
    }
    if(na_poti)return naj;
    else return -1;
}

int travelTime(int N, int M, int L, int A[], int B[], int T[]) {
    for(int i=0;i<M;i++){
        gozd[A[i]].push_back(B[i]);
        teza[A[i]].push_back(T[i]);
        gozd[B[i]].push_back(A[i]);
        teza[B[i]].push_back(T[i]);
    }
    memset(obiskan,0,sizeof(obiskan));
    int rezultat = 0;
    vector<int> polmeri;
    for(int i=0;i<N;i++){
        if(obiskan[i])continue;
        pair<int,int> konec = razdalja(i,-1);
        pair<int,int> drug_konec = razdalja(konec.second,-1);//drug_konec je zdaj (premer, drug konec premera)
        rezultat = max(rezultat, drug_konec.first);
        polmeri.push_back(polmer(konec.second,-1,drug_konec.second,drug_konec.first,0));
    }
    sort(polmeri.begin(),polmeri.end());
    reverse(polmeri.begin(),polmeri.end());
    if(polmeri.size()>1)
        rezultat = max(polmeri[0]+polmeri[1]+L,rezultat);
    if(polmeri.size()>2)
        rezultat = max(polmeri[2]+polmeri[1]+2*L,rezultat);
    return rezultat;
}