#include <iostream>
#include <fstream>
#include <limits.h>
#define infinit 100005

using namespace std;

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

int viz[2000],d[2000],t[2000],n,m,x,y,z,a[2000][2000];

void dijkstra(int x0){

    int i,j,minn,ok,k;
    for(i=1;i<=n;i++){

        d[i]=a[x0][i];
        t[i]=x0;
        viz[i]=0;
    }

    t[x0]=0;
    viz[x0]=1;
    ok=1;
    while(ok){
        minn=infinit;
        for(i=1;i<=n;i++)
            if(!viz[i] && minn>d[i]){
                minn=d[i];
                k=i;
            }
            if(minn!=infinit){
                viz[k]=1;
                for(i=1;i<=n;i++)
                    if(!viz[i] && d[i]>d[k]+a[k][i]){
                        d[i]=d[k]+a[k][i];
                        t[i]=k;

                    }
            }
            else    ok=0;
    }
}

/*void drum(int x){
    if(t[x]){
        drum(t[x]);

        g<<","<<x;
    }
    else    g<<x;
}
*/

int main(){

    int k;
    f>>n>>m;
    f>>k;
    for(int i=1;i<=m;i++){
        f>>x>>y>>z;
        a[x][y]=z;
    }


    for(int i=1;i<=n;i++)
        for(int j=1;j<=n;j++)
            if(a[i][j]==0)  a[i][j]=infinit;


    dijkstra(1);
    g<<d[n];
    return 0;
}