方法爲二分答案。

我們暫且不考慮最優解的問題，假設A爲一個可行解。可以知道如果A成立，則B(B>=A)一定成立。這說明解具有單調性，即所有可行解是一個單調序列。我們模仿二分查找的方法，對答案進行二分嘗試，對最優解逐步逼近。

對於這道題，假設A=4這個解成立，則說明頂點1到N之間必存在某路徑，滿足這條路徑中長度大於4的邊不超過K條（如果超過K條，4就不是去除K條以外的最大值了，與題意矛盾）。

1. 判斷給定的A是否爲可行解，即求從頂點1到頂點N的某條路徑上，長度大於A的邊最少有多少條。如果最少的條數小於等於K，則A爲一個可行解。
2. 對於求最少的條數，可以在原圖的基礎上構造一個新圖，改變邊權。如果一條邊原來的權值大於A，則在新圖中將其權值設爲1；如果一條邊原來的權值小於等於A，則在新圖中將其權值設爲0。
3. 然後求出從頂點1到N的最短路徑長度D，D即爲從頂點1到頂點N的某條路徑上，長度大於A的邊最少有多少條。
4. 如果D<=K，則A爲可行解。

/*
ID: cmykrgb1
PROG: phoneline
LANG: C++
*/

#include <iostream>
#define MAX 1001
#define MAXP 10001
#define MAXL 1000000
using namespace std;

class tQueue
{
public:
    class linklist
    {
    public:
        linklist* next;
        int value;
        linklist()
        {
            next=0;
            value=0;
        }
    };
    linklist *first,*last;
    int size;
    bool inq[MAX];
    void add(int p)
    {
        if (size==0)
            first=last=new linklist;
        else
            last=last->next=new linklist;
        last->value=p;
        inq[p]=true;
        size++;
    }
    int del()
    {
        int rtn=first->value;
        inq[rtn]=false;
        linklist *tfirst=first;
        first=first->next;
        delete tfirst;
        size--;
        return rtn;
    }
    void reset()
    {
        size=0;
        first=last=0;
        memset(inq,0,sizeof(inq));
    }
    tQueue()
    {
        reset();
    }
};

class list
{
public:
    list *next;
    int p;
    list(int &tp)
    {
        p=tp;
        next=0;
    }
};

class tadjl
{
public:
    list *first,*last;
    tadjl()
    {
        first=last=0;
    }
    void ins(int p)
    {
        if (first)
            last=last->next=new list(p);
        else
            first=last=new list(p);
    }
};

tadjl adjl[MAX];
tQueue Q;
int dis[MAX][MAX],sp[MAX];
int N,P,K;

void init()
{
    int i,a,b,v;
    freopen("phoneline.in","r",stdin);
    freopen("phoneline.out","w",stdout);
    cin >> N >> P >> K;
    for (i=1;i<=P;i++)
    {
        scanf("%d%d%d",&a,&b,&v);
        adjl[a].ins(b);
        adjl[b].ins(a);
        dis[a][b]=dis[b][a]=v;
    }
}

bool check(int A)
{
    list *k;
    int i,j,v;
    Q.reset();
    Q.add(1);
    memset(sp,0xf,sizeof(sp));
    sp[1]=0;
    while (Q.size)
    {
        i=Q.del();
        for (k=adjl[i].first;k;k=k->next)
        {
            j=k->p;
            v=dis[i][j];
            if (v>A)
                v=1;
            else
                v=0;
            if (sp[i]+v<sp[j])
            {
                sp[j]=sp[i]+v;
                if (!Q.inq[j])
                    Q.add(j);
            }
        }
    }
    return sp[N]<=K;
}

void solve()
{
    int a,b,m;
    a=0;
    b=MAXL;
    while (a<b)
    {
        m=(a+b)/2;
        if (check(m))
            b=m;
        else
            a=m+1;
    }
    if (a==MAXL)
        a=-1;
    cout << a << endl;
}

int main()
{
    init();
    solve();
    return 0;
}