#include<bits/stdc++.h>
using namespace std;

const long long MaxN = 2e5 + 5, MaxW = 15, MaxState = 2, INF = 1e18;

long long n,m,d[MaxN][MaxW][MaxState];
vector<pair<long long,long long>> vt[MaxN];

void dijikstra()
{
    priority_queue<tuple<long long,long long,long long,long long>,
                   vector<tuple<long long,long long,long long,long long>>,
                   greater<tuple<long long,long long,long long,long long>>> pq;

    pq.push({0,1,0,1});

    while(!pq.empty())
    {
        long long du = get<0>(pq.top());
        long long u = get<1>(pq.top());
        long long w = get<2>(pq.top());
        long long state = get<3>(pq.top());
        pq.pop();

        if(du != d[u][w][state]) continue;

        for(auto x : vt[u])
        {
            long long v = x.first;
            long long weight_v = x.second;

            if(state == 0)
            {
                if(d[v][weight_v][1] > du + w * weight_v)
                {
                    d[v][weight_v][1] = du + w * weight_v;
                    pq.push({d[v][weight_v][1],v,weight_v,1});
                }
            }

            if(state == 1)
            {
                if(d[v][weight_v][0] > du)
                {
                    d[v][weight_v][0] = du;
                    pq.push({d[v][weight_v][0],v,weight_v,0});
                }
            }
        }
    }
}

void input()
{
    cin >> n >> m;

    for(long long i=1; i<=m; i++)
    {
        long long u,v,w;
        cin >> u >> v >> w;

        vt[u].push_back({v,w});
        vt[v].push_back({u,w});
    }
}

void output()
{
    for(long long i=1; i<=n; i++)
    {
        for(long long j=0; j<MaxW; j++)
        {
            for(long long k=0; k<=1; k++)
            {
                d[i][j][k] = INF;
            }
        }
    }

    d[1][0][1] = 0;

    dijikstra();

    long long ans = INF;

    for(long long i=0; i<MaxW; i++)
    {
        ans = min(ans,d[n][i][1]);
    }

    if(ans == INF)
    {
        cout << -1;
        return;
    }

    cout << ans;
}

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    input();
    output();
}