#include <bits/stdc++.h>
using namespace std;
using pii=pair<int,int>;
using ll=long long;

const int maxn=101;
vector<pii> adj[maxn];
int k, n;
pii a[maxn];
queue<int> q;
bool inq[maxn];
ll ans=-1;

bool bfs(int i, int mx){
    for (int j=1;j<=n;j++) {
        a[j]={-1,-1};
    }
    a[i]={1, mx};
    q.push(i);
    inq[i]=true;
    while (q.size()) {
        int v = q.front();
        q.pop();
        inq[v]=false;
        for (auto to:adj[v]){
            if (to.second >mx) continue;
            int to1 = to.first;
            int b1 = a[v].first, b2=a[v].second;
            if (b2 < to.second) {
                b1++;
                b2=mx-to.second;
            } else b2-=to.second;
            pii prev=a[to1];
            if (a[to1].first != -1 && a[to1].first > b1) a[to1]={b1, b2};
            else if(a[to1].first==b1&&a[to1].second < b2) a[to1]={b1, b2};
            else if(a[to1].first==-1)a[to1]={b1, b2};
            if (prev!=a[to1] && inq[to1]==false) {q.push(to1);inq[to1]=true;}
        }
    }
    for (int j=1;j<=n;j++) {
        auto& p=a[j];
        if (p.first > k || p.first==-1) {
            return false;
        }
    }
    return true;
}

int main() {
    int m;
    cin>>n>>m>>k;
    for (int i=0;i<m;i++) {
        int a, b, c; cin>>a>>b>>c;
        adj[a].push_back({b, c});
        adj[b].push_back({a, c});
    }
    ll l = 1,r=1e9;
    while (l<r){
        ll mid=l + (r - l) / 2;
        bool ok=true;
        for(int i = 1;i<=n;i++) {
            if (!bfs(i, mid)) {ok=false; break;}
        }
        if (ok) {
            r=mid;
            ans=mid;
        } else{
            l=mid+1;
        }
    }
    cout << ans << '\n';
}

/*
4 4 2   
1 2 1
2 3 2
3 4 3
4 1 4
*/