#include <cstdio>
#include <algorithm>
#include <iostream>
#include "grader.h"
#include <vector>

using namespace std;

#define forit(it, S) for(__typeof((S).begin()) it = (S).begin(); it != (S).end(); ++it)
#define maxn 200001
#define F first
#define S second

vector <int> tree[maxn];
int cnt, d[maxn], d1[maxn], q[maxn], radius[maxn], p[maxn], d2[maxn], last, was[maxn], par[maxn];
vector <pair <int, int> > g[maxn];
bool used[maxn];
pair <int, int> diam[maxn];

int most_distant(int x)
{
    ++last;
    int l = 0, r = 1, res = x;
    d2[x] = 0;
    q[r] = x;
    was[x] = last;

    while (l < r)
    {
        int v = q[++l];

        forit(it, g[v])
            if (was[it -> F] != last)
            {
                was[it -> F] = last;
                q[++r] = it -> F;
                d2[it -> F] = d2[v] + it -> S;
                if (d2[res] < d2[it -> F])
                    res = it -> F;
                par[it -> F] = v;
            }
    }

    return res;
}

int get_center(int x)
{
    most_distant(diam[x].F);

    vector <int> path;

    for (int v = diam[x].S; v != diam[x].F; v = par[v])
        path.push_back(v);

    path.push_back(diam[x].F);

    int res = 0;

    if (path.size() & 1)
        return d2[most_distant(path[(path.size() + 1) / 2 - 1])];
    else
    {
        int u = d2[most_distant(path[path.size() / 2 - 1])];
        int v = d2[most_distant(path[path.size() / 2])];

        return min(u, v);
    }
}

void calc_radius(int x)
{
    int fr = most_distant(tree[x][0]);
    int sc = most_distant(fr);

    diam[x] = make_pair(fr, sc);
    radius[x] = get_center(x);
}

bool cmp(int a, int b)
{
    return radius[a] > radius[b];
}

void dfs(int v)
{
    tree[cnt].push_back(v);
    used[v] = 1;

    forit(it, g[v])
        if (!used[it -> F])
            dfs(it -> F);
}

int travelTime(int n, int m, int l, int a[], int b[], int t[])
{
    for (int i = 0; i < m; ++i)
    {
        g[a[i]].push_back(make_pair(b[i], t[i]));
        g[b[i]].push_back(make_pair(a[i], t[i]));
    }

    cnt = 0;

    for (int i = 0; i < n; ++i)
        if (!used[i])
        {
            ++cnt;
            dfs(i);
            calc_radius(cnt);
        }

    if (cnt == 1)
        return d2[most_distant(diam[1].F)];

    for (int i = 1; i <= cnt; ++i)
        p[i] = i;

    sort(p + 1, p + cnt + 1, cmp);

    int ans = radius[p[1]] + radius[p[2]] + l;

    if (cnt > 2)
        ans = max(ans, radius[p[2]] + radius[p[3]] + 2 * l);

    for (int i = 1; i <= cnt; ++i)
        ans = max(ans, d2[most_distant(diam[i].F)]);

    return ans;
};