// #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;
std::vector<pli> to[N];
typedef int64_t T;
void add(int x, int y, T val)
{
    to[x].push_back({val, y});
}
namespace Graph1
{
    typedef std::pair<int64_t, int32_t> pli;
    std::vector<pli> to[N];
    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));
                }
        }
    }
}
namespace Graph2
{
    typedef int64_t T;
    typedef std::pair<int64_t, int32_t> pli;
    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;
        add(x, y, v);
        add(y, x, v);
        vec.push_back(Edge{x, y, v});
    }
    Graph1::shortest_path(1);
    Graph2::shortest_path(n);
    ll ans = llinf;
    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)
            ans = min(ans, max1 + w);
        if (max2 <= w)
            ans = min(ans, max2 + w);
    }
    cout << ans << endl;
}
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int t = 1;
    while (t-- > 0)
    {
        work();
    }
}

answer.code: In function ‘void Graph2::shortest_path(int32_t)’:
answer.code:77:33: error: no matching function for call to ‘max(Graph2::T&, std::tuple_element<0, std::pair<long long int, long long int> >::type&)’
   77 |                 if (dis[y] > max(dis[x], val))
      |                              ~~~^~~~~~~~~~~~~
In file included from /usr/include/c++/13/algorithm:60,
                 from /usr/include/x86_64-linux-gnu/c++/13/bits/stdc++.h:51,
                 from answer.code:2:
/usr/include/c++/13/bits/stl_algobase.h:257:5: note: candidate: ‘template<class _Tp> constexpr const _Tp& std::max(const _Tp&, const _Tp&)’
  257 |     max(const _Tp& __a, const _Tp& __b)
      |     ^~~
/usr/include/c++/13/bits/stl_algobase.h:257:5: note:   template argument deduction/substitution failed:
answer.code:77:33: note:   deduced conflicting types for parameter ‘const _Tp’ (‘long int’ and ‘std::tuple_element<0, std::pair<long long int, long long int> >::type’ {aka ‘long long int’})
   77 |                 if (dis[y] > max(dis[x], val))
      |                              ~~~^~~~~~~~~~~~~
/usr/include/c++/13/bits/stl_algobase.h:303:5: note: candidate: ‘template<class _Tp, class _Compare> constexpr const _Tp& std::max(const _Tp&, const _Tp&, _Compare)’
  303 |     max(const _Tp& __a, const _Tp& __b, _Compare __comp)
      |     ^~~
/usr/include/c++/13/bits/stl_algobase.h:303:5: note:   template argument deduction/substitution failed:
answer.code:77:33: note:   deduced conflicting types for parameter ‘const _Tp’ (‘long int’ and ‘std::tuple_element<0, std::pair<long long int, long long int> >::type’ {aka ‘long long int’})
   77 |                 if (dis[y] > max(dis[x], val))
      |                              ~~~^~~~~~~~~~~~~
In file included from /usr/include/c++/13/algorithm:61:
/usr/include/c++/13/bits/stl_algo.h:5795:5: note: candidate: ‘template<class _Tp> constexpr _Tp std::max(initializer_list<_Tp>)’
 5795 |     max(initializer_list<_Tp> __l)
      |     ^~~
/usr/include/c++/13/bits/stl_algo.h:5795:5: note:   template argument deduction/substitution failed:
answer.code:77:33: note:   mismatched types ‘std::initializer_list<_Tp>’ and ‘long int’
   77 |                 if (dis[y] > max(dis[x], val))
      |                              ~~~^~~~~~~~~~~~~
/usr/include/c++/13/bits/stl_algo.h:5805:5: note: candidate: ‘template<class _Tp, class _Compare> constexpr _Tp std::max(initializer_list<_Tp>, _Compare)’
 5805 |     max(initializer_list<_Tp> __l, _Compare __comp)
      |     ^~~
/usr/include/c++/13/bits/stl_algo.h:5805:5: note:   template argument deduction/substitution failed:
answer.code:77:33: note:   mismatched types ‘std::initializer_list<_Tp>’ and ‘long int’
   77 |                 if (dis[y] > max(dis[x], val))
      |                              ~~~^~~~~~~~~~~~~
answer.code:79:33: error: no matching function for call to ‘max(Graph2::T&, std::tuple_element<0, std::pair<long long int, long long int> >::type&)’
   79 |                     dis[y] = max(dis[x], val);
      |                              ~~~^~~~~~~~~~~~~
/usr/include/c++/13/bits/stl_algobase.h:257:5: note: candidate: ‘template<class _Tp> constexpr const _Tp& std::max(const _Tp&, const _Tp&)’
  257 |     max(const _Tp& __a, const _Tp& __b)
      |     ^~~
/usr/include/c++/13/bits/stl_algobase.h:257:5: note:   template argument deduction/substitution failed:
answer.code:79:33: note:   deduced conflicting types for parameter ‘const _Tp’ (‘long int’ and ‘std::tuple_element<0, std::pair<long long int, long long int> >::type’ {aka ‘long long int’})
   79 |                     dis[y] = max(dis[x], val);
      |                              ~~~^~~~~~~~~~~~~
/usr/include/c++/13/bits/stl_algobase.h:303:5: note: candidate: ‘template<class _Tp, class _Compare> constexpr const _Tp& std::max(const _Tp&, const _Tp&, _Compare)’
  303 |     max(const _Tp& __a, const _Tp& __b, _Compare __comp)
      |     ^~~
/usr/include/c++/13/bits/stl_algobase.h:303:5: note:   template argument deduction/substitution failed:
answer.code:79:33: note:   deduced conflicting types for parameter ‘const _Tp’ (‘long int’ and ‘std::tuple_element<0, std::pair<long long int, long long int> >::type’ {aka ‘long long int’})
   79 |                     dis[y] = max(dis[x], val);
      |                              ~~~^~~~~~~~~~~~~
/usr/include/c++/13/bits/stl_algo.h:5795:5: note: candidate: ‘template<class _Tp> constexpr _Tp std::max(initializer_list<_Tp>)’
 5795 |     max(initializer_list<_Tp> __l)
      |     ^~~
/usr/include/c++/13/bits/stl_algo.h:5795:5: note:   template argument deduction/substitution failed:
answer.code:79:33: note:   mismatched types ‘std::initializer_list<_Tp>’ and ‘long int’
   79 |                     dis[y] = max(dis[x], val);
      |                              ~~~^~~~~~~~~~~~~
/usr/include/c++/13/bits/stl_algo.h:5805:5: note: candidate: ‘template<class _Tp, class _Compare> constexpr _Tp std::max(initializer_list<_Tp>, _Compare)’
 5805 |     max(initiali...