#include<iostream>
#include<fstream>
using namespace std;
ifstream f("cim.in");
ofstream g("cim.out");
int d[100],s[100],t[100],r,n,m,k,orase[100],x,y,z,cost[100][100];
int main()
{
int i,j,mini,poz,p,e=0;
f>>n>>m>>k;
if(k==0)
{
for(i=1;i<=n;i++)
for(j=1;j<=n;j++)
if(i==j)cost[i][j]=0;
else
cost[i][j]=32000;
for(i=1;i<=m;i++)
{ f>>x>>y>>z;
cost[x][y]=z;
cost[y][x]=z;}
/*for(i=1;i<=n;i++)
{
for(j=1;j<=n;j++)
g<<cost[i][j]<<" ";
g<<endl;
}*/
r=1;s[r]=1;
for(i=1;i<=n;i++)
{
d[i]=cost[r][i];
if(i!=r)
if(d[i]<32000)
t[i]=r;
}
for(i=1;i<=n-1;i++)
{
mini=32000;
for(j=1;j<=n;j++)
if(s[j]==0)
if(d[j]<mini)
{
mini=d[j];
poz=j;
}
s[poz]=1;
for(j=1;j<=n;j++)
if(s[j]==0)
if(d[j]>d[poz]+cost[poz][j])
{
d[j]=d[poz]+cost[poz][j];
t[j]=poz;
}}
}
g<<d[n];
}