#include <iostream>
#include <fstream>

using namespace std;
struct pont
{
    bool volt=false;
    int ertek;
};
int main()
{
    int n,m,k;
    ifstream f("ubuntzei.in.txt");
    f>>n >>m >>k;
    int csucsm[n][n];
    for(int i=0;i<n;i++)
    {
        for(int j=0;j<n;j++)
        {
            csucsm[i][j]=0;
        }
    }
    for(int i=0;i<m;i++)
    {
        int x,y,z;
        f>> x >> y >>z;
        csucsm[x-1][y-1]=z;
        csucsm[y-1][x-1]=z;
    }
    pont tav[n];
    for(int i=0;i<n;i++)
    {
        tav[i].ertek=0;
    }
    int start=1;
    for(int i=0;i<n;i++)
    {
        if(csucsm[start-1][i]!=0)
        {
            tav[i].ertek=csucsm[start-1][i];
        }
    }
    tav[start-1].volt=true;
    int p;
    for(int i=0;i<n;i++)
    {
        int sz=999999;
        for(int j=0;j<n;j++)
        {
            if((tav[j].ertek<sz and tav[j].ertek!=0)and !tav[j].volt)
            {
                sz=tav[j].ertek;
                p=j;
            }
        }
        for(int j=0;j<n;j++)
        {
            if(csucsm[p][j]!=0)
            {
                if((tav[p].ertek+csucsm[p][j] < tav[j].ertek)or tav[j].ertek==0)
                {
                    tav[j].ertek=tav[p].ertek + csucsm[p][j];
                }
            }
        }
        tav[p].volt=true;
    }
    tav[start-1].ertek=-1;
    ofstream of("ubuntzei.out.txt");
    of << tav[n-1].ertek;
}