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

using namespace std;
#define int long long
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 Graph1
{
    typedef int64_t T;
    typedef std::pair<int64_t, int32_t> pli;
    std::vector<pli> to[N];
    void add(int x, int y, T val)
    {
        to[x].push_back({val, y});
    }
    bool vis[N];
    T 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(0, from));
        memset(dis, 0x3f, sizeof dis);
        memset(vis, 0, sizeof vis);
        dis[from] = 0;
        while (!q.empty())
        {
            auto [nowval, x] = q.top();
            q.pop();
            if (vis[x])
                continue;
            vis[x] = 1;
            for (auto [val, y] : to[x])
                if (dis[y] > dis[x] + val)
                {
                    dis[y] = dis[x] + val;
                    q.push(std::make_pair(dis[y], y));
                }
        }
    }
}
namespace Graph2
{
    typedef int64_t T;
    typedef std::pair<int64_t, int32_t> pli;
    std::vector<pli> to[N];
    void add(int x, int y, T val)
    {
        to[x].push_back({val, y});
    }
    bool vis[N];
    T 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(0, from));
        memset(dis, 0x3f, sizeof dis);
        memset(vis, 0, sizeof vis);
        dis[from] = 0;
        while (!q.empty())
        {
            auto [nowval, x] = q.top();
            q.pop();
            if (vis[x])
                continue;
            vis[x] = 1;
            for (auto [val, y] : to[x])
                if (dis[y] > max(dis[x], val))
                {
                    dis[y] = max(dis[x], val);
                    q.push(std::make_pair(dis[y], y));
                }
        }
    }
}
void work()
{
    cin >> n >> m;
    struct Edge
    {
        int x, y, w;
        bool operator<(Edge b)
        {
            return w < b.w;
        }
    };
    vector<Edge> vec;
    for (int i = 0; i < m; i++)
    {
        int x, y, v;
        cin >> x >> y >> v;
        Graph1::add(x, y, v);
        Graph1::add(y, x, v);
        Graph2::add(x, y, v);
        Graph2::add(y, x, v);
        vec.push_back(Edge{x, y, v});
    }
    Graph1::shortest_path(1);
    Graph2::shortest_path(n);
    int ans = 2e9;
    for (auto [x, y, w] : vec)
    {
        int max1 = max(Graph1::dis[x], Graph2::dis[y]);
        int max2 = max(Graph2::dis[x], Graph1::dis[y]);
        if (max1 <= w || max2 <= w)
            ans = min(ans, min(max1, max2) + w);
        if ((x == 1 && y == n) || (x == n && y == 1))
            ans = min(ans, w);
    }
    cout << ans << endl;
}
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int t = 1;
    while (t-- > 0)
    {
        work();
    }
}