#include <fstream>
#define nmax 50002
#define mmax 250002
#define inf 200000000



using namespace std;

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

int x,y,z;
struct muchie
{
    int x,y,l;
};
muchie G[mmax];
int D[nmax];
int n,m;

int main()
{f>>n>>m;
int i,ok=0;
for(i=1;i<=m;++i)
{
  f>>G[i].x>>G[i].y>>G[i].l;


}
for(i=2;i<=n;i++) if(D[i]==0) D[i]=inf;

while(ok==0)
{
    ok=1;
    for(i=1;i<=m;++i)
    if(D[G[i].y]>D[G[i].x]+G[i].l)
    {D[G[i].y]=D[G[i].x]+G[i].l;
     ok=0;

    }
}
g<<D[n-1]+D[n-2];
//for(i=2;i<=n;++i)
//{
//    if(D[i]!=inf) g<<D[i]<<' ';
//          else g<<0<<' ';
//}
    return 0;
}