#include<iostream>
#include<fstream>
using namespace std;
ifstream f("cim.in");
ofstream g("cim.out");
int d[2001],s[2001],r,n,m,k,orase[16],x,y;
long cost[2001][2001],z;
int main()
{
int i,j,mini,poz;
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]=100001;
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];
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];
}}
g<<d[n];}
f.close();
g.close();
return 0;

}