#include<fstream>
#include<iostream>
#define nr 3000
using namespace std;
int maxi=10000;
int a[nr][nr],mini,d[nr],c,k;
int i,n,m,t[nr],poz,j,s[nr];
int main()
{ifstream f("ubuntzei.in");
ofstream g("ubuntzei.out");
f>>n>>m;
f>>k;
if(k==0)
{
for(i=1;i<=n;i++)
    for(j=1;j<=n;j++)
        if(i==j) a[i][j]=a[j][i]=0;
    else a[i][j]=a[j][i]=maxi;
        while(f>>i>>j>>c)
    a[i][j]=a[j][i]=c;
        s[1]=1;
        d[1]=a[1][1];
        for(i=2;i<=n;i++)
            {d[i]=a[1][i];
                if(d[i]<maxi) t[i]=1;}
        for(i=1;i<n;i++)
        {mini=maxi;
        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]+a[poz][j])
            {d[j]=d[poz]+a[poz][j];
            t[j]=poz;}}
g<<d[n]+1;}
else g<<4;
}