#include<iostream>
#include<fstream>
#include<queue>
#include<cstdlib>
  
using namespace std;
  
ifstream fin ("ubuntzei.in");
ofstream fout ("ubuntzei.out");
 
struct Nod
{
    int nod, cost;
    bool operator < (const Nod& e) const
    {
        return cost > e.cost;
    }
};
  
vector <Nod> L[2050];
int n,m, cost[2050], k;
  
priority_queue <Nod> q;
  
void Citire()
{
  int x,y,costt;
  Nod w;
  fin >> n >> m;
  fin >> k;
  if (k!=0) exit(0);
  for (int i=1; i<=m; i++)
   {
      fin >> x >> y >> costt;
      w.nod=y;
      w.cost=costt;    
      L[x].push_back(w);
   }
}
  
void Lee_Bellman_Ford_BFS_Dijkstra()
{
  int i,j,k,costt;
  Nod w,w1;
  w.nod=1;
  w.cost=0;
  q.push(w);
  cost[1]=0;
    
  while (!q.empty())
 {
   w = q.top();
   q.pop();
     
   k = w.nod;
   for (int j=0; j<L[k].size(); j++)
       {
            i = L[k][j].nod; costt = L[k][j].cost;
              
            if (!cost[i] || cost[i] >= cost[k] + costt)
               {
                   cost[i] = cost[k] + costt;
                   w1.nod=i;
                   w1.cost=cost[i];
                   q.push(w1);
               }
       }
 } 
}
  
void Print_that()
{
 fout << cost[n] << "\n";
 fout << "\n";
}
  
int main ()
{
 Citire();
 Lee_Bellman_Ford_BFS_Dijkstra();
 Print_that();
 fin.close();
 fout.close();
 return 0;
}