Proficient.
Put your skills to the test.

Problem summary

A directed dependency A→B with threshold C means specialist A needs B to act first when radiation is at least C. Find the maximum integer radiation allowing all specialists to act, or −1 if every level is feasible. Also output the lexicographically smallest valid order at that level.

Constraints

1 ≤ N ≤ 1000; 0 ≤ M ≤ 10000; 1 ≤ C ≤ 100000; no self-loops or duplicate directed edges.

Worked example

An independently prepared example for this explanation.

4 3
2 1 6
4 2 6
3 1 6

-1
1 2 3 4

Solution analysis

1. At radiation R keep exactly the dependencies with C≤R. Reverse each into the execution-order edge B→A. Feasibility means this graph is acyclic. Kahn’s algorithm detects this by counting removed vertices.
2. As radiation grows, edges are only added, so feasibility is monotone. First check the full graph at the maximum threshold. If it is acyclic the answer is −1; otherwise binary-search the greatest feasible radiation from 0 through that threshold.
3. For the final feasible graph use a min-priority queue of currently available specialists. Always take the smallest number. In the sample, specialist 1 is initially the only prerequisite root; choosing 2 before 3 then makes 4 available, producing 1,2,3,4.

Why it works

A set of precedence constraints admits an ordering exactly when its graph is acyclic, and Kahn’s algorithm removes all vertices exactly in that case. Monotonicity justifies the binary search. For lexicographic minimality, any valid continuation must begin with an available vertex; selecting the smallest such vertex minimizes the first differing position, and the same argument applies after its removal.

Watch out. Reverse the input dependency for execution order. A threshold is active at equality. If adding edges at threshold C first creates a cycle, the largest feasible integer radiation is C−1.

An independently written complete program with standard headers.

#include<algorithm>
#include<functional>
#include<iostream>
#include<queue>
#include<vector>
using namespace std;
struct Edge{
    int dependent,prerequisite,threshold;
};
int main(){
    // Compute the exact archive answer using the method explained above.
    int n,m;
    cin>>n>>m;
    vector<Edge>edges(m);
    int maximum=0;
    for(Edge&e:edges){
        cin>>e.dependent>>e.prerequisite>>e.threshold;
        e.dependent--;
        e.prerequisite--;
        maximum=max(maximum,e.threshold);
    }
    auto order=[&](int radiation){
        vector<vector<int>>graph(n);
        vector<int>degree(n,0);
        for(Edge e:edges){
            if(e.threshold<=radiation){
                graph[e.prerequisite].push_back(e.dependent);
                degree[e.dependent]++;
            }
        }
        priority_queue<int,vector<int>,greater<int>>ready;
        for(int v=0;v<n;v++){
            if(degree[v]==0){
                ready.push(v);
            }
        }
        vector<int>result;
        while(!ready.empty()){
            int v=ready.top();
            ready.pop();
            result.push_back(v);
            for(int u:graph[v]){
                degree[u]--;
                if(degree[u]==0){
                    ready.push(u);
                }
            }
        }
        return result;
    };
    bool unlimited=static_cast<int>(order(maximum).size())==n;
    int low=0;
    int high=maximum;
    if(!unlimited){
        while(low<high){
            int middle=low+(high-low+1)/2;
            if(static_cast<int>(order(middle).size())==n){
                low=middle;
            }
            else{
                high=middle-1;
            }
        }
    }
    int radiation=unlimited?maximum:low;
    cout<<(unlimited?-1:radiation)<<'\n';
    vector<int>result=order(radiation);
    for(int i=0;i<n;i++){
        if(i!=0){
            cout<<' ';
        }
        cout<<result[i]+1;
    }
    cout<<'\n';
}