//
// 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, dis[N], vis[N];

struct edge {
    int v, val;

    bool operator<(const edge &x) const {
        if (v != x.v) return v < x.v;
        return val < x.val;
    }
};

vector<edge> e[N];

void dij(int s) {
    priority_queue<pll> q;
    int tag, val;
    q.push({0, s});
    dis[s] = 0;
    while (!q.empty()) {
        int u = q.top().second;
        q.pop();
        if (vis[u]) continue;
        vis[u] = 1;
        sort(e[u].begin(), e[u].end());
        tag = -1;
        while (!e[u].empty()) {
            if (e[u].back().v == tag) e[u].pop_back();
            else {
                int siz = e[u].size();
                if (e[u][siz - 1].v == e[u][siz - 2].v) {
                    val = e[u][siz - 1].val + e[u][siz - 2].val;
                    tag = e[u][siz - 1].v;
                    e[u].pop_back();
                    e[u].pop_back();
                } else {
                    val = e[u][siz - 1].val;
                    tag = e[u][siz - 1].v;
                    e[u].pop_back();
                }
                if (dis[tag] > dis[u] + val) {
                    dis[tag] = dis[u] + val;
                    if (!vis[tag])
                        q.push({-dis[tag], tag});
                }
            }
        }
    }
}

inline void Zlin() {
    cin >> n >> m;
    for (int i = 1, u, v, val; i <= m; i++) {
        cin >> u >> v >> val;
        e[u].push_back({v, val});
        e[v].push_back({u, val});
    }
    for (int i = 1; i <= n; i++) vis[i] = 0, dis[i] = inf;
    dij(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;
}