#include<cmath>
#include<cstdio>
#include<iostream>
#include<cstdlib>
#include<algorithm>
#include<cstring>
#include<map>
#include<queue>
#include<set>
#include<vector>
#include<bitset>
#include<time.h>
#define rg register
using namespace std;
typedef long long ll;
const int maxn=200005,maxk=15;
int n,m,k,cnt,head[maxn],vis[maxn],shunxu[maxk],jinchu[maxk];//0表示头进尾出
ll dis[maxk*2][maxk*2],ans=1e18;
clock_t kaishi,xianzai;
struct edge
{
    int to,next;
    ll quan;
}e[maxn<<1];
struct suki
{
    int u,v;
    ll disu[maxn],disv[maxn],changdu;
}s[maxk];
struct node
{
    int id;
    ll juli;
    bool operator < (const node &a) const
    {
        return juli>a.juli;
    }
};
inline char nc()
{
    static char buf[100000],*p1=buf,*p2=buf;
    return p1==p2&&(p2=(p1=buf)+fread(buf,1,100000,stdin),p1==p2)?EOF:*p1++;
}
inline int read()
{
    char ch=nc();
    int sum=0;
    while(!(ch>='0'&&ch<='9'))
    {
        ch=nc();
        if(ch==EOF) 
            return EOF;
    }
    while(ch>='0'&&ch<='9')
    {
        sum=sum*10+ch-48;
        ch=nc();
        if(ch==EOF) 
            return EOF;
    }
    return sum;
}
 
 
inline void write(ll a)
{
    if(a<0)
    {
        char a='-',b='1';
        putchar(a);
        putchar(b);
    }
    else
    {
        if(a>=10)
            write(a/10);
        putchar(a%10+'0');
    }
}
inline void add(int from,int to,ll quan)
{
    e[++cnt]=(edge){to,head[from],quan};
    head[from]=cnt;
}
inline void dijkstra(int start,ll kyori[])
{
    memset(vis,0,sizeof(vis));
    for(rg int i=1;i<=n;++i)
        kyori[i]=1e18;
    kyori[start]=0;
    priority_queue<node>q;
    q.push((node){start,0});
    while(!q.empty())
    {
        int now=q.top().id;
        q.pop();
        if(vis[now])
            continue;
        vis[now]=1;
        for(rg int i=head[now];i;i=e[i].next)
        {
            int to=e[i].to;
            if(kyori[to]>kyori[now]+e[i].quan)
            {
                kyori[to]=kyori[now]+e[i].quan;
                q.push((node){to,kyori[to]});
            }
        }
    }
}
inline void GKD()
{
    ll kotae=0;
    random_shuffle(shunxu+1,shunxu+k+1);
    for(rg int i=1;i<=k;++i)
        jinchu[i]=rand()%2;
    kotae+=dis[0][shunxu[1]+k*jinchu[1]];
    for(rg int i=1;i<k;++i)
    {
        int now=shunxu[i],f=jinchu[i],next=shunxu[i+1],ff=jinchu[i+1];
        kotae+=s[now].changdu;
        kotae+=dis[now+k*(!f)][next+k*ff];
    }
    kotae+=s[shunxu[k]].changdu;
    kotae+=dis[shunxu[k]+k*(!jinchu[k])][0];
    ans=min(ans,kotae);
}
signed main()
{
    kaishi=clock();
    memset(dis,0x3f,sizeof(dis));
    dis[0][0]=0;
    n=read(),m=read(),k=read();
    for(rg int i=1;i<=m;++i)
    {
        int u=read(),v=read();
        ll w=read();
        add(u,v,w),add(v,u,w);
        if(i<=k)
            s[i].u=u,s[i].v=v,s[i].changdu=w;
    }
    for(rg int i=1;i<=k;++i)
    {
        dijkstra(s[i].u,s[i].disu);
        dijkstra(s[i].v,s[i].disv);
        for(rg int j=1;j<=k;++j)
        {
            dis[i][j]=s[i].disu[s[j].u];
            dis[i][j+k]=s[i].disu[s[j].v];
            dis[i+k][j]=s[i].disv[s[j].u];
            dis[i+k][j+k]=s[i].disv[s[j].v];
            dis[i][0]=dis[0][i]=s[i].disu[1];
            dis[i+k][0]=dis[0][i+k]=s[i].disv[1];
        }
    }
    for(int i=1;i<=k;++i)
        shunxu[i]=i;
    xianzai=clock();
//  cout<<(double)(xianzai-kaishi)/CLOCKS_PER_SEC<<endl;
    while(1)
    {
        GKD();
        xianzai=clock();
        if((double)(xianzai-kaishi)/CLOCKS_PER_SEC>=2.9)
            break;
    }
    write(ans);
    return 0;
}