Problem E

#include <iostream>
#include <queue>
#include <algorithm>

using namespace std;

struct road {
    int u, t, w;
};

vector<road> g[N];

void dijkstra(int x) {
    for (int i = 2; i <= n; i++)
        dist[i] = INF;
    priority_queue<cell, vector<cell>, CellComparator> q;///{dist[v], v}
    for (int i = 1; i <= n; i++)
        q.push({dist[i], i});

    while (!q.empty()) {
        int d = q.top().dist;
        int v = q.top().v;
        q.pop();

        if (d != dist[v])///= d > dist[v], so we already used v before
            continue;

        for (auto [u, t, w] : g[v])
            if (dist[u] > dist[v] + t && w >= x) {
                dist[u] = dist[v] + t;
                q.push({dist[u], u});
                ///different pairs for the same u
            }
    }
}

int main()
{
    ///read
    ...


    int l = 0, r = 1'000'000'001;
    while (l < r - 1) {
        int m = (l + r) / 2;
        if (dijkstra(m) <= 525600)
            l = m;
        else
            r = m;
    }
    cout << l;
    return 0;
}