1100E - Andrew and Taxi cf-1100E

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

const int N = 1e5 + 5 ;

typedef long long ll;

struct Edge {
    int u, v, w;
}E[N];

int n, m;
vector<int> G[N];
int vis[N];

bool cycle;

void dfs(int u) {
    vis[u] = 1;
    for(int v : G[u]) {
        if (vis[v] == 0) {
            dfs(v);
        }
        else if (vis[v] == 1) {
            cycle = true;
            return;
        }
    }
    vis[u] = 2;
}

bool ok(int lim) {
    for(int i = 1; i <= n; i++) G[i].clear();
    for(int i = 1; i <= m; i++) {
        if (E[i].w > lim) {
            G[E[i].u].push_back(E[i].v);
        }
    }
    cycle = false;
    memset(vis,0,sizeof vis);
    for(int i = 1; i <= n; i++) {
        if (vis[i] == 0) {
            dfs(i);
        }
    }
    return !cycle;
}

vector<int> sorted;
int ord[N];

void topSort(int u) {
    vis[u] = 1;
    for(int v : G[u]) {
        if (vis[v]==0) {
            topSort(v);
        }
    }
    sorted.push_back(u);
    ord[u] = (int)sorted.size();
}

void F(int lim) {
    for(int i = 1; i <= n; i++) G[i].clear();
    for(int i = 1; i <= m; i++) {
        if (E[i].w > lim) {
            G[E[i].u].push_back(E[i].v);
        }
    }
    memset(vis,0,sizeof vis);
    for(int i = 1; i <= n; i++) {
        if (vis[i]==0) topSort(i);
    }
    vector <int> change;
    for(int i = 1; i <= m ; i++) {
        if (E[i].w <= lim) {
            int u = E[i].u , v = E[i].v;
            if (ord[u] < ord[v]) {
                change.push_back(i);
            }
        }
    }
    cout << lim << " " << (int)change.size() << endl ;
    for(int x : change) printf ("%d " , x);
}


int main() {
    cin >> n >> m ;
    for(int i = 1; i <= m; i++) {
        scanf("%d %d %d",&E[i].u,&E[i].v,&E[i].w);
    }
    int lo = 0, hi = 1e9 + 10;
    while(hi > lo) {
        int mid = (hi+lo)/2;
        if(ok(mid)) hi = mid;
        else lo = mid+1;
    }
    F(lo);
}