#include "iostream"
#include "cstring"
#include "queue"
using namespace std;
#define INF 999999999
#define eMax 505
#define nMax 105
bool vis[nMax];
int dis[2][nMax], num, rec[nMax], n, m;
struct Node
{
    int u, v, w, pre;
}e[eMax*2];
void Init(int u, int v, int w)
{
    e[num].u = u;
    e[num].v = v;
    e[num].w = w;
    e[num].pre = rec[u];
    rec[u] = num++;
}
void spfa(int s, int p)
{
    memset(vis, false, sizeof(vis));
    dis[p][s] = 0;
    queue<int> q;
    q.push(s);
    while(!q.empty())
    {
        s = q.front();
        q.pop();
        vis[s] = false;
        int j, v;
        for(j=rec[s]; j!=-1; j=e[j].pre)
        {
            v = e[j].v;
            if(dis[p][s] + e[j].w < dis[p][v])
            {
                dis[p][v]=dis[p][s]+e[j].w;
                if(!vis[v])
                {
                    vis[v] = true;
                    q.push(v);
                }
            }
        }
    }
}
int main()
{
    int u, v, w;
    while(cin>>n>>m)
    {
        num = 0;
        memset(rec, -1, sizeof(rec));
        memset(dis, 0x3f, sizeof(dis));
        int ans = INF;
        while(m--)
        {
            cin>>u>>v>>w;
            Init(u, v, w);
            Init(v, u, w);
        }
        spfa(1, 0);
        spfa(n, 1);
        for(int i=0; i<num; i++)
            if(dis[0][e[i].u]+dis[1][e[i].v] < ans)
                ans = dis[0][e[i].u]+dis[1][e[i].v];
        if(ans < INF) cout<<ans<<endl;
        else cout<<"-1"<<endl;
    }
}