#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 n,k;
pii best[maxn];
bool inq[maxn];

bool bfs(int i,int mx){
    for(int j=1;j<=n;j++) {
        best[j]={-1,-1};
    }
    best[i]={1, mx};
    queue<int> q;
    q.push(i);
    inq[i]=true;
    while(q.size()) {
        int v=q.front();q.pop();
        inq[v]=false;
        for(auto [u,cost]:adj[v]){
            if(cost>mx)continue;
            auto [vb1,vb2]=best[v];
            if(vb2<cost){
                vb1++;
                vb2=mx-cost;
            }else vb2-=cost;
            auto [ub1,ub2]=best[u];
            if(ub1==-1)best[u]={vb1,vb2};
            else if(ub1>vb1)best[u]={vb1,vb2};
            else if(ub1==vb1&&ub2<vb2)best[u]={vb1,vb2};
            if(make_pair(ub1,ub2)!=best[u]&&inq[u]==false){
                q.push(u);
                inq[u]=true;
            }
        }
    }
    for(int j=1;j<=n;j++) {
        auto [b1,b2]=best[j];
        if(b1>k||b1==-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)/2;
        bool ok=true;
        for(int i=1;i<=n;i++)
            if(!bfs(i,mid)){
                ok=false;break;
            }
        if(ok){
            r=mid;
        }else l=mid+1;
    }
    cout<<r<<'\n';
}

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