#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;
} 
