100460C.cc

#include <cstdio>
#include <vector>
#include <utility>
#include <queue>
#include <algorithm>
#define N 100002
#define F first
#define S second
#define INF 0x3f3f3f3f


using namespace std;

typedef pair<int, int> pii;
typedef pair<pii, int> state;

vector<pii> gr[N];
int dis1[N], dis2[N];

void di(int x,int n, int* v) {
  priority_queue<pii, vector<pii>, greater<pii> > pq;
  for (int i = 1; i <= n; ++i)
    v[i] = INF;
  pq.push(pii(0, x));
  v[x] = 0;
  while (!pq.empty()) {
    int q = pq.top().S;
    int d = pq.top().F;
    pq.pop();
    if (v[q] > d) {
      continue;
    }
    for (pii nx: gr[q]){
      int u = nx.F, w = nx.S;
      if (max(w, v[q]) < v[u]) {
        v[u] = max(w, v[q]);
        pq.push(pii(v[u], u));
      }
    }
  }
}

int main() {
  int n, m;
  scanf("%d%d", &n, &m);
  if (n == 1) {
    printf("0\n");
    return 0;
  }
  for (int i = 0; i < m; ++i) {
    int a, b, c;
    scanf("%d%d%d", &a, &b, &c);
    gr[a].push_back(pii(b, c));
    gr[b].push_back(pii(a, c));
  }
  di(1, n, dis1);
  di(n, n, dis2);
  int ans = INF;
  for (int v = 1; v <= n; ++v) {
    for (pii nx: gr[v]) {
      int u = nx.F, w = nx.S;
      vector<int> ord;
      ord.push_back(w);
      ord.push_back(dis1[v]);
      ord.push_back(dis2[u]);
      sort(ord.begin(), ord.end());
      if (ord.back() != INF) {
        ans = min(ans, ord[1]);
      }
    }
  }
  printf("%d\n", ans);
  return 0;
}