let INF = 0x3f3f3f3f;
let N = 510;

let edge = [];
let dist = new Int32Array(N).fill(INF);


let bellman_ford = () => {
    dist[1] = 0;
    let backup = []; //备份数组
    for (let i = 0; i < k; i++) {
        backup = dist.slice(); //备份，限定边数，最短路径结果可能和不限制的不同
        for (let i = 0; i < m; i++) {
            let e = edge[i];
            let a = e[0],
                b = e[1],
                c = e[2];
            //如果不使用备份数据Math.min(dist[b], dist[a] + c);，更新时用到的数据可能是本次循环刚刚更新的数据，就无法体现出限定边数
            dist[b] = Math.min(dist[b], backup[a] + c);
        }
    }
}


let n = 0,
    m = 0,
    k = 0;

let buf = '';
process.stdin.on('readable', function () {
    let chunk = process.stdin.read();
    if (chunk) buf += chunk.toString();
});
let getInputNums = line => line.split(' ').filter(s => s !== '').map(x => parseInt(x));
let getInputStr = line => line.split(' ').filter(s => s !== '');
process.stdin.on('end', function () {
    buf.split('\n').forEach(function (line, lineIdx) {
        if (lineIdx === 0) {
            n = getInputNums(line)[0];
            m = getInputNums(line)[1];
            //限制k条边
            k = getInputNums(line)[2];
        } else if (lineIdx <= m) {
            let arr = getInputNums(line);
            let a = arr[0];
            let b = arr[1];
            let c = arr[2];
            edge.push([a, b, c]);
            if (lineIdx === m) {
                bellman_ford();
                if (dist[n] > parseInt(INF / 2)) console.log(-1);
                else console.log(dist[n]);
            }
        }
    });
});