//
// Created by Zlin on 2024/10/19.
//

#include "bits/stdc++.h"

using namespace std;

typedef double db;
typedef long double ldb;
typedef long long ll;
typedef unsigned long long ull;
typedef vector<int> vi;
typedef vector<long long> vll;
typedef pair<int, int> pii;
typedef pair<long long, long long> pll;

const int N = 3e5 + 5;
const ll inf = 1e17;

int n, m, vis[N];
ll dis[N];
struct edge {
    int v, val;
};
vector<edge> e[N];

vi ee[N];
map<pii, int> top1, top2, used;

void Add(int u, int v) {
    int val = top1[{u, v}] + top2[{u, v}];
    e[u].push_back({v, val});
}

void add(int u, int v, int val) {
    if (!top1[{u, v}]) {
        top1[{u, v}] = val;
    } else if (!top2[{u, v}] || top2[{u, v}] < val) {
        top2[{u, v}] = val;
        if (top1[{u, v}] < top2[{u, v}]) {
            top2[{u, v}] = top1[{u, v}];
            top1[{u, v}] = val;
        }
    }
}

struct node {
    ll val;
    int pos;

    bool operator<(const node &x) const {
        return val > x.val;
    }
};

inline void dijkstra(int s) {
    priority_queue<node> q;
    dis[s] = 0;
    q.push({0, s});
    while (!q.empty()) {
        node u = q.top();
        q.pop();
        int x = u.pos;
        if (vis[x]) continue;
        vis[x] = 1;
        for (auto it: e[x]) {
            int y = it.v;
            if (dis[y] > dis[x] + it.val) {
                dis[y] = dis[x] + it.val;
                if (!vis[y])
                    q.push({dis[y], y});
            }
        }
    }
}

inline void Zlin() {
    cin >> n >> m;
    for (int i = 1, u, v, val; i <= m; i++) {
        cin >> u >> v >> val;
        add(u, v, val);
        add(v, u, val);
        if (!used[{u, v}]) {
            ++used[{u, v}];
            ++used[{v, u}];
            ee[u].push_back(v);
            ee[v].push_back(u);
        }
    }
    queue<int> q;
    q.push(1);
    int u;
    while (!q.empty()) {
        u = q.front();
        q.pop();
        if (vis[u]) continue;
        vis[u] = 1;
        for (int v: ee[u]) {
            Add(u, v);
            if (!vis[v])
                q.push(v);
        }
    }
    for (int i = 1; i <= n; i++) vis[i] = 0, dis[i] = inf;
    dijkstra(1);
    cout << dis[n] << '\n';
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr), cout.tie(nullptr);
    int ttt = 1;
//    cin >> ttt;
    while (ttt--) Zlin();
    return 0;
}