#include<iostream>
#include<fstream>
#include<vector>
using namespace std;
ifstream in ("ubuntzei.in");
ofstream out ("ubuntzei.in");

int main (){
  int n,m,k,i,j,t;
  in>>n>>m>>k;
  vector<vector<int> > a(n,vector<int>(n));
  vector<vector<int> > d(n,vector<int>(n,10000000));

  for(i=0;i<m;i++)
  {
    in>>j>>t;
    j--;t--;
    in>>a[j][t];
    a[t][j] = a[j][t];
    d[t][j] = a[t][j];
    d[j][t] = a[j][t];
  }

  //for(i=0;i<n;i++)
  //{
    //for(j=0;j<n;j++)
      //cout<<a[i][j]<<" ";
    //cout<<"\n";
  //}
  //
  for(k=0;k<n;k++)
    for(i=0;i<n;i++)
      for(j=0;j<n;j++)
        if(d[i][j] > d[i][k] + d[k][j])
        {
          d[i][j] = d[j][k] + d[k][j];
        }

  out<<d[0][n-1];

  return 0;
}