LightOJ - Not the Best

#include <bits/stdc++.h>
using namespace std;

const int maxN = 5e3 + 100;
vector<pair<int64_t,int64_t>> adj[maxN];
int64_t dist[2][maxN];

void dijkstra (int source,int n,bool yes) {
    for (int i = 1; i <= n; ++i) dist[yes][i] = 1e12;
    dist[yes][source] = 0;
    priority_queue<pair<int64_t,int64_t>> pq;
    pq.push(make_pair(0,source));
    while (!pq.empty()) {
        int64_t node_cost = abs(pq.top().first);
        int64_t node = pq.top().second;
        pq.pop();
        if (dist[yes][node] < node_cost) continue;
        for (pair<int64_t,int64_t> child : adj[node]) {
            if (child.second + node_cost < dist[yes][child.first]) {
                dist[yes][child.first] = child.second + node_cost;
                pq.push(make_pair(-dist[yes][child.first],child.first));
            }
        }
    }
}

int main () {
     ios::sync_with_stdio(false);
     cin.tie(nullptr);
     cout.tie(nullptr);
     int T;
     cin >> T;
     for (int test_case = 1; test_case <= T; ++test_case) {
         for (int i = 1; i < maxN; ++i) adj[i].clear();
         int n,m;
         cin >> n >> m;
         vector<pair<pair<int64_t,int64_t>,int64_t>> edges;
         for (int i = 1; i <= m; ++i) {
             int64_t u,v,cost;
             cin >> u >> v >> cost;
             adj[u].push_back(make_pair(v,cost));
             adj[v].push_back(make_pair(u,cost));
             edges.push_back(make_pair(make_pair(u,v),cost));
         }
         dijkstra(1,n,0);
         dijkstra(n,n,1);
         int64_t first_s = dist[0][n];
         int64_t second_s = 1e12;
         for (pair<pair<int64_t,int64_t>,int64_t> e : edges) {
             int64_t current = min(dist[0][e.first.first] + dist[1][e.first.second],dist[1][e.first.first] + dist[0][e.first.second]);
             if (current + e.second > first_s) {
                 second_s = min(second_s,current + e.second);
             }
             second_s = min(second_s,current + (e.second * 3));
         }
         cout << second_s << '\n';
     }
     //cerr << "Time elapsed :" << clock() * 1000.0 / CLOCKS_PER_SEC << " ms" << '\n';
}