Andrew prefers taxi to other means of transport, but recently most taxi drivers have been acting inappropriately. In order to earn more money, taxi drivers started to drive in circles. Roads in Andrew's city are one-way, and people are not necessary able to travel from one part to another, but it pales in comparison to insidious taxi drivers.

The mayor of the city decided to change the direction of certain roads so that the taxi drivers wouldn't be able to increase the cost of the trip endlessly. More formally, if the taxi driver is on a certain crossroads, they wouldn't be able to reach it again if he performs a nonzero trip. 

Traffic controllers are needed in order to change the direction the road goes. For every road it is known how many traffic controllers are needed to change the direction of the road to the opposite one. It is allowed to change the directions of roads one by one, meaning that each traffic controller can participate in reversing two or more roads.

You need to calculate the minimum number of traffic controllers that you need to hire to perform the task and the list of the roads that need to be reversed.


-----Input-----

The first line contains two integers $n$ and $m$ ($2 \leq n \leq 100\,000$, $1 \leq m \leq 100\,000$) — the number of crossroads and the number of roads in the city, respectively.

Each of the following $m$ lines contain three integers $u_{i}$, $v_{i}$ and $c_{i}$ ($1 \leq u_{i}, v_{i} \leq n$, $1 \leq c_{i} \leq 10^9$, $u_{i} \ne v_{i}$) — the crossroads the road starts at, the crossroads the road ends at and the number of traffic controllers required to reverse this road.


-----Output-----

In the first line output two integers the minimal amount of traffic controllers required to complete the task and amount of roads $k$ which should be reversed. $k$ should not be minimized.

In the next line output $k$ integers separated by spaces — numbers of roads, the directions of which should be reversed. The roads are numerated from $1$ in the order they are written in the input. If there are many solutions, print any of them.


-----Examples-----
Input
5 6
2 1 1
5 2 6
2 3 2
3 4 3
4 5 5
1 5 4

Output
2 2
1 3 
Input
5 7
2 1 5
3 2 3
1 3 3
2 4 1
4 3 5
5 4 1
1 5 3

Output
3 3
3 4 7 


-----Note-----

There are two simple cycles in the first example: $1 \rightarrow 5 \rightarrow 2 \rightarrow 1$ and $2 \rightarrow 3 \rightarrow 4 \rightarrow 5 \rightarrow 2$. One traffic controller can only reverse the road $2 \rightarrow 1$ and he can't destroy the second cycle by himself. Two traffic controllers can reverse roads $2 \rightarrow 1$ and $2 \rightarrow 3$ which would satisfy the condition.

In the second example one traffic controller can't destroy the cycle $ 1 \rightarrow 3 \rightarrow 2 \rightarrow 1 $. With the help of three controllers we can, for example, reverse roads $1 \rightarrow 3$ ,$ 2 \rightarrow 4$, $1 \rightarrow 5$.

Source: codeforces | Difficulty: HARD
Tags: Sorting

Graph algorithms

Graph traversal


Solutions:
from collections import deque
(N, M) = map(int, input().split())
table = []
for i in range(M):
	(s, t, c) = map(int, input().split())
	(s, t) = (s - 1, t - 1)
	table.append((s, t, c))

def check(k):
	Lin = [0] * N
	edge = [[] for i in range(N)]
	for (s, t, c) in table:
		if c > k:
			Lin[t] += 1
			edge[s].append(t)
	Haco = deque()
	ans = []
	for i in range(N):
		if Lin[i] == 0:
			ans.append(i)
			Haco.append(i)
	while Haco:
		x = Haco.pop()
		for y in edge[x]:
			Lin[y] -= 1
			if Lin[y] == 0:
				ans.append(y)
				Haco.append(y)
	return ans
ma = 10 ** 9 + 7
mi = -1
while ma - mi > 1:
	mid = (ma + mi) // 2
	if len(check(mid)) == N:
		ma = mid
	else:
		mi = mid
ans = check(ma)
dd = {}
for i in ans:
	dd[ans[i]] = i
num = 0
answer = []
for i in range(M):
	(s, t, c) = table[i]
	if dd[s] > dd[t] and c <= ma:
		answer.append(i + 1)
		num += 1
print(ma, num)
print(' '.join(map(str, answer)))


import sys
from operator import itemgetter
readline = sys.stdin.readline

def topological_sort(E, D):
	D = D[:]
	n = len(E)
	Q = [i for i in range(n) if D[i] == 0]
	L = []
	while Q:
		p = Q.pop()
		L.append(p)
		for vf in E[p]:
			D[vf] -= 1
			if not D[vf]:
				Q.append(vf)
	if len(L) != n:
		return False
	return L
(N, M) = map(int, readline().split())
Edge = [None] * M
for m in range(M):
	(a, b, c) = map(int, readline().split())
	a -= 1
	b -= 1
	Edge[m] = (c, m + 1, a, b)
Edge.sort(key=itemgetter(0), reverse=True)
ok = 0
ng = M + 1
while abs(ok - ng) > 1:
	med = (ok + ng) // 2
	Edge2 = [[] for _ in range(N)]
	Dim2 = [0] * N
	for i in range(med):
		(_, _, a, b) = Edge[i]
		Edge2[a].append(b)
		Dim2[b] += 1
	if topological_sort(Edge2, Dim2):
		ok = med
	else:
		ng = med
Edge2 = [[] for _ in range(N)]
Dim = [0] * N
for i in range(ok):
	(_, _, a, b) = Edge[i]
	Edge2[a].append(b)
	Dim[b] += 1
L = topological_sort(Edge2, Dim)
Linv = [None] * N
for i in range(N):
	Linv[L[i]] = i
Ans = []
ans = 0
if ok < M:
	ans = Edge[ok][0]
	for i in range(ok, M):
		(c, m, a, b) = Edge[i]
		if Linv[a] > Linv[b]:
			Ans.append(m)
print(ans, len(Ans))
print(*Ans)


import os, sys
from io import BytesIO, IOBase

def check(n, mid, path, cost, num):
	(ans, poi, visi) = ([], [0] * n, [0] * n)
	for i in range(n):
		if visi[i]:
			continue
		(visi[i], st, st1) = (2, [i], [])
		while len(st):
			(x, y) = (st[-1], path[st[-1]])
			if poi[x] == len(y):
				visi[x] = 1
				st1.append(st.pop())
			else:
				(i, j) = (y[poi[x]], cost[st[-1]][poi[x]])
				poi[x] += 1
				if j <= mid:
					continue
				if visi[i] == 2:
					return -1
				if not visi[i]:
					st.append(i)
					visi[i] = 2
		ans += st1
	start = [0] * n
	for (ind, i) in enumerate(reversed(ans)):
		start[i] = ind
	(poi, visi, fin) = ([0] * n, [0] * n, [])
	for i in range(n):
		if visi[i]:
			continue
		(visi[i], st) = (1, [i])
		while len(st):
			(x, y) = (st[-1], path[st[-1]])
			if poi[x] == len(y):
				st.pop()
			else:
				(i, j, k) = (y[poi[x]], cost[st[-1]][poi[x]], num[st[-1]][poi[x]])
				poi[x] += 1
				visi[i] = 1
				st.append(i)
				if start[i] < start[x] and j <= mid:
					fin.append(k)
	return fin

def main():
	(n, m) = map(int, input().split())
	path = [[] for _ in range(n)]
	cost = [[] for _ in range(n)]
	num = [[] for _ in range(n)]
	for _ in range(m):
		(u1, v1, c1) = map(int, input().split())
		path[u1 - 1].append(v1 - 1)
		cost[u1 - 1].append(c1)
		num[u1 - 1].append(_ + 1)
	(hi, lo) = (10 ** 9, 0)
	while hi >= lo:
		mid = (hi + lo) // 2
		z = check(n, mid, path, cost, num)
		if z == -1:
			lo = mid + 1
		else:
			hi = mid - 1
			ans = mid
			an = z
	print(ans, len(an))
	print(*an)
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')
main()


import sys, math, itertools
from collections import Counter, deque, defaultdict
from bisect import bisect_left, bisect_right
from heapq import heappop, heappush, heapify, nlargest
from copy import deepcopy
mod = 10 ** 9 + 7
INF = float('inf')

def inp():
	return int(sys.stdin.readline())

def inpl():
	return list(map(int, sys.stdin.readline().split()))

def inpl_1():
	return list(map(lambda x: int(x) - 1, sys.stdin.readline().split()))

def inps():
	return sys.stdin.readline()

def inpsl(x):
	tmp = sys.stdin.readline()
	return list(tmp[:x])

def err(x):
	print(x)
	exit()
(n, m) = inpl()
abc = [inpl() for _ in range(m)]

def sol(X):
	g = [[] for _ in range(n)]
	ny = [0] * n
	for (a, b, c) in abc:
		if c > X:
			g[a - 1].append(b - 1)
			ny[b - 1] += 1
	seen = [0] * n
	q = deque()
	for (i, x) in enumerate(ny):
		if x == 0:
			q.append(i)
			seen[i] = 1
	while q:
		v = q.popleft()
		for u in g[v]:
			if seen[u]:
				continue
			ny[u] -= 1
			if ny[u] == 0:
				q.append(u)
				seen[u] = 1
	return all(seen)

def sol2(X):
	g = [[] for _ in range(n)]
	ny = [0] * n
	for (a, b, c) in abc:
		if c > X:
			g[a - 1].append(b - 1)
			ny[b - 1] += 1
	tps = [-1] * n
	T = 0
	seen = [0] * n
	q = deque()
	for (i, x) in enumerate(ny):
		if x == 0:
			q.append(i)
			seen[i] = 1
	while q:
		v = q.popleft()
		tps[v] = T
		T += 1
		for u in g[v]:
			if seen[u]:
				continue
			ny[u] -= 1
			if ny[u] == 0:
				q.append(u)
				seen[u] = 1
	return tps
ok = 10 ** 9 + 10
ng = -1
while abs(ok - ng) > 1:
	mid = (ok + ng) // 2
	if sol(mid):
		ok = mid
	else:
		ng = mid
res = []
tps = sol2(ok)
for (i, (a, b, c)) in enumerate(abc):
	if c <= ok:
		if tps[a - 1] > tps[b - 1]:
			res.append(i + 1)
print(ok, len(res))
print(*res)


import sys
input = sys.stdin.readline
from collections import *

def judge(x):
	ins = [0] * n
	outs = defaultdict(list)
	for (u, v, c) in edges:
		if c > x:
			ins[v] += 1
			outs[u].append(v)
	q = deque([v for v in range(n) if ins[v] == 0])
	cnt = 0
	while q:
		v = q.popleft()
		cnt += 1
		for nv in outs[v]:
			ins[nv] -= 1
			if ins[nv] == 0:
				q.append(nv)
	return cnt == n

def binary_search():
	(l, r) = (0, 10 ** 9 + 10)
	while l <= r:
		m = (l + r) // 2
		if judge(m):
			r = m - 1
		else:
			l = m + 1
	return l
(n, m) = map(int, input().split())
edges = []
idx = defaultdict(lambda : deque([]))
for i in range(m):
	(u, v, c) = map(int, input().split())
	u -= 1
	v -= 1
	edges.append((u, v, c))
	idx[10 ** 6 * u + v].append(i + 1)
k = binary_search()
ins = [0] * n
outs = defaultdict(list)
removed = []
for (u, v, c) in edges:
	if c > k:
		ins[v] += 1
		outs[u].append(v)
	else:
		removed.append((u, v))
q = deque([v for v in range(n) if ins[v] == 0])
order = [-1] * n
cnt = 0
while q:
	v = q.popleft()
	order[v] = cnt
	cnt += 1
	for nv in outs[v]:
		ins[nv] -= 1
		if ins[nv] == 0:
			q.append(nv)
change = []
for (u, v) in removed:
	if order[v] < order[u]:
		change.append(idx[10 ** 6 * u + v].popleft())
print(k, len(change))
print(*change)


import copy
import sys

def find_loop(g, w, k, n):
	visited = [False] * n
	visited_int = [False] * n
	for i in range(n):
		if visited[i]:
			continue
		stack = [g[i][:]]
		path = [i]
		visited[i] = True
		visited_int[i] = True
		while stack:
			if not stack[-1]:
				stack.pop()
				visited_int[path[-1]] = False
				path.pop()
				continue
			nxt = stack[-1][-1]
			stack[-1].pop()
			if w[path[-1], nxt] <= k:
				continue
			if visited_int[nxt]:
				return True
			if visited[nxt]:
				continue
			visited[nxt] = True
			visited_int[nxt] = True
			stack.append(g[nxt][:])
			path.append(nxt)
	return False

def top_sort(g, w, k, n):
	visited = [False] * n
	order = [-1] * n
	cnt = 0
	for i in range(n):
		if visited[i]:
			continue
		stack = [g[i][:]]
		path = [i]
		visited[i] = True
		while stack:
			if not stack[-1]:
				order[path[-1]] = cnt
				path.pop()
				stack.pop()
				cnt += 1
				continue
			nxt = stack[-1][-1]
			stack[-1].pop()
			if w[path[-1], nxt] <= k:
				continue
			if visited[nxt]:
				continue
			visited[nxt] = True
			stack.append(g[nxt][:])
			path.append(nxt)
	to_reverse = []
	for (a, b) in w.items():
		if b > k:
			continue
		if order[a[0]] < order[a[1]]:
			to_reverse.append(a)
	return to_reverse
(n, m) = map(int, input().split())
w = {}
g = [[] for _ in range(n)]
w_tmp = {}
c_m = 0
kk = [0]
lines = sys.stdin.readlines()
for (i, line) in enumerate(lines):
	(u, v, c) = map(int, line.split())
	g[u - 1].append(v - 1)
	if (u - 1, v - 1) in w.keys():
		w[u - 1, v - 1] = max(w[u - 1, v - 1], c)
	else:
		w[u - 1, v - 1] = c
	if (u - 1, v - 1) in w_tmp.keys():
		w_tmp[u - 1, v - 1].append(str(i + 1))
	else:
		w_tmp[u - 1, v - 1] = [str(i + 1)]
	kk.append(c)
kk.sort()
(l, r) = (0, len(kk))
if not find_loop(g, w, kk[l], n):
	print(0, 0)
	exit(0)
if find_loop(g, w, kk[-1], n):
	kkk = kk[-1]
else:
	while l + 1 != r:
		m = int((l + r) / 2)
		if find_loop(g, w, kk[m], n):
			l = m
		else:
			r = m
	kkk = kk[l + 1]
to_reverse = top_sort(g, w, kkk, n)
num = 0
s = []
for t in to_reverse:
	num += len(w_tmp[t])
	s.extend(w_tmp[t])
print(kkk, num)
print(' '.join(s))