#include <iostream>
#include <fstream>
#define MAXX 200000

using namespace std;

ifstream f("ubuntzei.in");
ofstream g("ubuntzei.out");

struct nod
{
    int inf,poz;
    nod *urm;
};

nod *G[2010];
int n,m;

void adaug_stiva(nod *&vf, int b, int c)
{
    nod *p=new nod;
    p->inf=c;
    p->poz=b;
    p->urm=vf;
    vf=p;
}

struct pque
{
    int inf,poz;
};
pque heap[10100];
int l;

void adaug_heap(int x, int y)
{
    heap[++l].inf=x;
    heap[l].poz=y;
    int z=l;
    while(heap[z].inf>heap[z/2].inf)
    {
        pque aux=heap[z];
        heap[z]=heap[z/2];
        heap[z/2]=aux;
        z=z/2;
    }
}

void elimin_heap()
{
    pque aux=heap[l];
    heap[l]=heap[l];
    heap[1]=aux;
    l--;
    int z=1;
    while(z <=l && ( heap[z].inf<heap[z*2].inf || heap[z].inf <heap[z*2+1].inf ) )
    {
        if(heap[z*2].inf>heap[z*2+1].inf)
        {
            pque aux=heap[z];
            heap[z]=heap[z*2];
            heap[z*2]=aux;
            z=z*2;
        }
        else
        {
            pque aux=heap[z];
            heap[z]=heap[z*2+1];
            heap[z*2+1]=aux;
            z=z*2+1;
        }
    }
}

int viz[2010],d[2010];

void Dijkstra(int x)
{
    for(int i=1;i<=n;i++)
        d[i]=MAXX;
    d[x]=0;
    viz[x]=1;
    {
        nod *it=G[x];
        while(it != 0)
        {
            d[it->poz]=it->inf;
            adaug_heap(-it->inf,it->poz);
            it=it->urm;
        }
    }
    while(l)
    {
        pque aux= heap[1];
        elimin_heap();
        int pct=aux.poz;
        if(viz[pct]==0)
        {
            viz[pct]=1;
            nod *it=G[pct];
            while(it != 0)
            {
                if(viz[it->poz]==0 && d[it->poz] > d[pct] + it->inf)
                {
                    d[it->poz] = d[pct] + it->inf;
                    adaug_heap(-d[it->poz],it->poz);
                }
                it=it->urm;
            }
        }
    }
    g<<d[n];

}

int main()
{
    int k;
    f>>n>>m>>k;
    for(int i=1;i<=n;i++)
        {
            G[i]=0;
        }
    for(int i=1;i<=m;i++)
    {
        int a,b,c;
        f>>a>>b>>c;
        adaug_stiva(G[a],b,c);
    }
    Dijkstra(1);
    return 0;
}