#include <bits/stdc++.h>
#define rep(i,a,b) for(int i=a;i<=b;i++)
#define ll long long
#define For(i,a,b) for(int i=a;i <b;i++)
#define vi vector<int>
#define ii pair<int,int>
#define lii pair<long long,int>
#define vii vector<ii>
#define vlii vector<lii>
#define pb push_back
#define mp make_pair
#define fi first
#define se second

using namespace std;
const int maxn=50001;
const int maxm=500000;

struct re
{
    int x,y,w;
};
int n,m;
ll d[maxn],res=1e12,dn[maxn];
bool ok;
vii a[maxn],ra[maxn];
bool vis[maxn];
re e[maxm];

void enter()
{
    freopen("SHORTEST.INP","r",stdin);
    cin >> n >> m;
    rep(i,1,m)
    {
        int x,y,w; cin >> x >> y >> w;
        e[i].x=x; e[i].y=y; e[i].w=w;
        a[x].pb(mp(y,w));
        ra[y].pb(mp(x,w));
    }
}

void dijkstra()
{
    priority_queue<lii,vlii,greater<lii> > heap;
    heap.push(mp(0,1));
    rep(i,1,n)
    {
        d[i]=1e12;
        dn[i]=1e12;
    }
    d[1]=0; dn[n]=0;
    while (!heap.empty())
    {
        int u=heap.top().se;
        heap.pop();
        if (vis[u]) continue;
        vis[u]=1;
        For(i,0,a[u].size())
        {
            int v=a[u][i].fi;
            int w=a[u][i].se;
            if (d[v]>d[u]+w)
            {
                d[v]=d[u]+w;
                heap.push(mp(d[v],v));
            }
        }
    }
    rep(i,1,n) vis[i]=0;
    while (!heap.empty()) heap.pop();
    heap.push(mp(0,n));
    while (!heap.empty())
    {
        int u=heap.top().se;
        heap.pop();
        if (vis[u]) continue;
        vis[u]=1;
        For(i,0,ra[u].size())
        {
            int v=ra[u][i].fi;
            int w=ra[u][i].se;
            if (dn[v]>dn[u]+w)
            {
                dn[v]=dn[u]+w;
                heap.push(mp(dn[v],v));
            }
        }
    }
}
void process()
{
    dijkstra();
    rep(i,1,m)
    {
        int x,y,w;
        x=e[i].x; y=e[i].y; w=e[i].w;
        if (d[x]+dn[y]+w>d[n]) res=min(res,d[x]+dn[y]+w);
    }
}

void out()
{
    freopen("SHORTEST.OUT","w",stdout);
    if (res==1e12) res=-1;
    cout << res;
}
int main()
{
    ios_base::sync_with_stdio(0);
    enter();
    process();
    out();
}