#include <iostream>
#include <vector>
#include <queue>
#include <climits>
using namespace std;
typedef long long ll;
const int MAXN = 5005;
const ll INF = 1e18;

vector<pair<int, int>> g[MAXN];
ll d1[MAXN], d2[MAXN]; // d1最短路，d2次短路

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    int N, R;
    cin >> N >> R;
    for(int i = 1; i <= R; ++i)
    {
        int a, b, d;
        cin >> a >> b >> d;
        g[a].emplace_back(b, d);
        g[b].emplace_back(a, d);
    }
    for(int i = 1; i <= N; ++i)
        d1[i] = d2[i] = INF;
    d1[1] = 0;
    // 修复greater，指定类型
    priority_queue<pair<ll, int>, vector<pair<ll, int>>, greater<pair<ll, int>>> q;
    q.emplace(0, 1);

    while(!q.empty())
    {
        pair<ll, int> cur = q.top();
        q.pop();
        ll dis = cur.first;
        int u = cur.second;

        if(dis > d2[u]) continue;
        for(size_t i = 0; i < g[u].size(); ++i)
        {
            int v = g[u][i].first;
            int w = g[u][i].second;
            ll nd = dis + w;
            if(nd < d1[v])
            {
                // 旧最短路降级为次短路
                d2[v] = d1[v];
                d1[v] = nd;
                q.emplace(d1[v], v);
                q.emplace(d2[v], v);
            }
            else if(nd > d1[v] && nd < d2[v])
            {
                d2[v] = nd;
                q.emplace(d2[v], v);
            }
        }
    }
    cout << d2[N] << endl;
    return 0;
}