Dijkstra-Atmost 1 edge

#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define int long long
#define INF LLONG_MAX
#define ar array
#define arr ar<int, 2>
#define IOS                         \
  std::ios::sync_with_stdio(false); \
  cin.tie(NULL);

int n, m;

vector<int> dijkstra(int v, vector<vector<ar<int, 2>>> &g)
{
  auto compare = [](const arr a, const arr b)
  {
    return a[1] > b[1];
  };
  priority_queue<arr, vector<arr>, decltype(compare)> pq(compare);
  vector<int> dis(n, INF);
  dis[v] = 0;
  pq.push({v, 0});
  while (!pq.empty())
  {
    auto tp = pq.top();
    pq.pop();
    int dist = tp[1];
    if (dis[tp[0]] != dist)
      continue;

    for (auto v : g[tp[0]])
    {
      int ver = v[0], weight = v[1];
      if (dis[ver] > dis[tp[0]] + weight)
      {
        dis[ver] = dis[tp[0]] + weight;
        pq.push({ver, dis[ver]});
      }
    }
  }
  return dis;
}
void init()
{
  cin >> n >> m;
  vector<vector<ar<int, 2>>> g, grev;
  vector<ar<int, 3>> edges;
  g.resize(n), grev.resize(n);
  for (int i = 0; i < m; i++)
  {
    int u, v, w;
    cin >> u >> v >> w;
    --u, --v;
    g[u].pb({v, w});
    grev[v].pb({u, w});
    edges.pb({u, v, w});
  }
  vector<int> a = dijkstra(0, g);
  vector<int> b = dijkstra(n - 1, grev);

  int ans = INF;

  for (auto edge : edges)
  {
    int st = edge[0], end = edge[1];
    if (a[st] != INF and b[end] != INF)
    {
      ans = min(ans, b[end] + a[st] + edge[2] / 2);
    }
  }
  cout << ans << endl;
}
int32_t main()
{
  IOS;
  init();
  return 0;
}