// #pragma GCC optimize("Ofast,no-stack-protector")
#include <bits/stdc++.h>

using namespace std;

const int N = 3e5 + 10;
const int inf = 1 << 30;
const long long llinf = 1ll << 60;
const double PI = acos(-1);

#define lowbit(x) (x & -x)
typedef long long ll;
typedef double db;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef pair<db, db> pdd;
typedef pair<ll, int> pli;

int n, m, k, q;
namespace Graph
{
    struct Price
    {
        int ge, le;
        Price() {}
        Price(int x, int y)
        {
            le = x;
            ge = y;
            if (le > ge)
                swap(le, ge);
        }
        bool operator<(Price b) const
        {
            if ((le + ge) != (b.le + b.ge))
                return (le + ge) < (b.le + b.ge);
            else
                return ge < b.ge;
        }
    };
    Price calc(Price a, int32_t b)
    {
        if (b > a.le)
            return Price(a.ge, b);
        return a;
    }
    typedef std::pair<Price, int32_t> pli;
    std::vector<pair<int, int>> to[N];
    void add(int x, int y, int val)
    {
        to[x].push_back({val, y});
    }
    bool vis[N];
    Price dis[N];
    void shortest_path(int32_t from)
    {
        // using Dijkstra
        std::priority_queue<pli, std::vector<pli>, std::greater<pli>> q;
        q.push(std::make_pair(Price(0, 0), from));
        fill(dis, dis + n + 1, Price((int)1e9, (int)1e9));
        memset(vis, 0, sizeof vis);
        dis[from] = Price(0, 0);
        while (!q.empty())
        {
            auto [nowval, x] = q.top();
            q.pop();
            if (vis[x])
                continue;
            vis[x] = 1;
            for (auto [val, y] : to[x])
            {
                auto now = calc(dis[x], val);
                if (now < dis[y])
                {
                    dis[y] = now;
                    q.push(std::make_pair(dis[y], y));
                }
            }
        }
    }
}

void work()
{
    cin >> n >> m;
    for (int i = 0; i < m; i++)
    {
        int x, y, v;
        cin >> x >> y >> v;
        Graph::add(x, y, v);
        Graph::add(y, x, v);
    }
    Graph::shortest_path(1);
    cout << Graph::dis[n].le + Graph::dis[n].ge << endl;
}
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int t = 1;
    while (t-- > 0)
    {
        work();
    }
}