#include<bits/stdc++.h>
using namespace std;
//#pragma GCC optimize(3,"Ofast","inline")
#define int long long
typedef long long ll;
const int inf=1e18;
const int mod=1e9+7;
const int N=105;
int n,m,kkk,ans,res,sum;
int a[N],e[N][N],dis[N][N];
struct Matrix{
    int a[105][105];
    Matrix(){
        for(int i=1;i<=n+1;i++)for(int j=1;j<=n+1;j++)a[i][j]=inf;
    }
};
Matrix operator *(const Matrix &X,const Matrix &Y){
    Matrix Z;
    for(int i=1;i<=n+1;i++)
        for(int j=1;j<=n+1;j++)
            for(int o=1;o<=n+1;o++)
                if(X.a[i][o]!=inf&&Y.a[o][j]!=inf)
                    Z.a[i][j]=min(Z.a[i][j],X.a[i][o]+Y.a[o][j]);
    return Z;
}
Matrix Matrix_qpow(Matrix x,long long y){
    Matrix res;
    for(int i=1;i<=n;i++)res.a[i][i]=0ll;
    while(y){
        if(y&1ll)res=res*x;
        x=x*x;
        y>>=1ll;
    }
    return res;
}
queue<int> q;
void spfa(int p){
    int vis[N],d[N],in[N],maxi[N];
    while(!q.empty())q.pop();
    for(int i=1;i<=n;i++)vis[i]=0,d[i]=inf,in[i]=0,maxi[i]=0;
    q.push(p);d[p]=0;
    while(!q.empty()){
        int u=q.front();
        q.pop();
        in[u]=0;
        for(int v=1;v<=n;++v){
            if(e[u][v]==inf)continue;
            if(d[u]+e[u][v]-max(maxi[u],e[u][v])*2<d[v]-maxi[v]*2){
                d[v]=d[u]+e[u][v];
                maxi[v]=max(maxi[u],e[u][v]);
                if(!in[v]){
                    q.push(v);
                    in[v]=1;
                }
            }
        }
    }
    for(int i=1;i<=n;i++)
        dis[p][i]=d[i]-maxi[i]*2;
}
signed main(){
    // freopen("in.in","r",stdin);
    // freopen("a.out","w",stdout);
    cin>>n>>m>>kkk;
    for(int i=1;i<=n;i++){
        for(int j=1;j<=n;j++){
            e[i][j]=inf,dis[i][j]=inf;
        }
    }
    for(int i=1,u,v;i<=m;i++){
        cin>>u>>v;
        cin>>e[u][v];
        dis[u][v]=e[u][v];
    }
    for(int k=1;k<=n;k++)
        for(int u=1;u<=n;u++)
            for(int v=1;v<=n;v++)
                dis[u][v]=min(dis[u][v],dis[u][k]+dis[k][v]);
    if(kkk==0){
        cout<<dis[1][n];
        return 0;
    }
    for(int i=1;i<=n;i++)
        spfa(i);
    Matrix A,B;
    for(int i=1;i<=n;i++)
        for(int j=1;j<=n;j++){
            if(dis[i][j]!=inf)B.a[i][j]=dis[i][j];
            else B.a[i][j]=inf;
        }
    for(int i=1;i<=n;i++)
        B.a[i][n+1]=B.a[i][n];
    B.a[n+1][n+1]=0;
    A.a[1][1]=0;
    // B.print();
    Matrix ANS=A*Matrix_qpow(B,kkk);
    cout<<ANS.a[1][n];
    return 0;
}
/*

*/
 
/*
文件名: p6190.cpp
创建时间: 2024-10-24 08:28:22
作者: nnn233
*/