#include<cstdio>
#include<climits>
#include<algorithm>
#include<cstring>
#include<queue>
using namespace std;
const int maxn=5005;
const int maxm=2e5+5;
const int INF=INT_MAX>>1;
struct Edge
{
    int to,cost,next;
};
struct node1
{
    int to;
    int g,f;
    bool operator <(const node1 &r)const
    {
        if(r.f==f) return r.g<g;
        return r.f<f;
    }
};
Edge edge[maxm];
int head[maxn];
int d[maxn];
bool SPFA (int s,int n,int head[],Edge edge[],int d[])
{
    int i,k;
    fill(d,d+n+1,INF);
    bool vis[maxn];
    int que[maxn];
    int iq=0;
    int top;
    int outque[maxn];
    memset(vis,0,sizeof(vis));
    memset(outque,0,sizeof(outque));
    que[iq++]=s;
    vis[s]=1;
    d[s]=0;
    i=0;
    while(i!=iq)
    {
        top=que[i];
        vis[top]=false;
        outque[top]++;
        if(outque[top]>n) return false;
        k=head[top];
        while(k>=0)
        {
            if(d[edge[k].to]-edge[k].cost>d[top])
            {
                d[edge[k].to]=edge[k].cost+d[top];
                if(!vis[edge[k].to])
                {
                    vis[edge[k].to]=true;
                    que[iq++]=edge[k].to;
                }
            }
            k=edge[k].next;
        }
        i++;
    }
    return true;
}
int a_star(int start,int End,int n,int k,int head[],Edge edge[],int d[])
{
    node1 e,ne;
    int cnt=0;
    priority_queue<node1> que;
    if(start==End) k++;
    if(d[start]==INF) return -1;
    e.to=start;
    e.g=0;
    e.f=e.g+d[e.to];
    que.push(e);
    while(!que.empty())
    {
        e=que.top();
        que.pop();
        if(e.to==End)cnt++;
        if(cnt==k)return e.g;
        for(int i=head[e.to]; i!=-1; i=edge[i].next)
        {
            ne.to=edge[i].to;
            ne.g=e.g+edge[i].cost;
            ne.f=ne.g+d[ne.to];
            que.push(ne);
        }

    }
    return -1;
}
void addedge(int from,int to,int cost,int &p)
{
    edge[p].to=to;
    edge[p].cost=cost;
    edge[p].next=head[from];
    head[from]=p++;
}
int main()
{
    int n,m;
    while(~scanf("%d%d",&n,&m))
    {
        memset(head,-1,sizeof(head));
        int x,y,cost;
        int p=0;
        for(int i=0; i<m; i++)
        {
            scanf("%d%d%d",&x,&y,&cost);
            addedge(x,y,cost,p);
            addedge(y,x,cost,p);
        }
        SPFA(n,n,head,edge,d);
        int len=a_star(1,n,n,2,head,edge,d);
        printf("%d\n",len);
    }
    return 0;
}