如下代码是可以通过本题的，但显然存在两个问题。

第一个问题是时间复杂度问题，在删除有间接路径的边这一部分，可以通过构造数据将枚举卡到 $\mathcal{O}(n ^ 2)$。（比如说菊花图）

第二个问题是正确性问题。本代码是过不了样例 2 的。称有向边 $u \to v$ 的起点为 $u$，终点为 $v$，新图中满足 $w_i = i$ 的边为“边 $i$”。在正确做法中，除了代码中已有的判断无解的方式，还需要判断在新图中，是否有若边 $x, y$ 起点相同，则在原图中可以到达 $x$ 点的点集和可以到达 $y$ 点的点集相同；若终点相同，则在原图中可以从 $x$ 点到达的点集和可以从 $y$ 点到达的点集相同。把样例加到测试点里就能卡了。

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

const int N = 20000 + 5;

vector<int> G[N], G2[N];
int h[N], t[N], build[N], total;

vector<int> cur;
int from, to, res;

void debug() {
	cout << "[from, to, <Vertex>] = [" << from << ", " << to << ", {";
	for(int i = 0; i < cur.size(); i++){
		cout << cur[i];
		if(i < cur.size() - 1) cout << ", "; 
	}
	cout << "}]\n"; 
}

void insert(){
	// debug();
	if(cur.empty()){
		if(!build[from] && !build[to])
			h[from] = ++total, t[from] = h[to] = ++total, t[to] = ++total, build[from] = build[to] = 1;
		else if(!build[from])
			h[from] = ++total, t[from] = h[to], build[from] = 1;
		else if(!build[to])
			h[to] = t[from], t[to] = ++total, build[to] = 1;
		else {
			if(t[from] != h[to])
				res = -1;
		}
		return;
	}
	if(!build[from])
		h[from] = ++total, t[from] = ++total, build[from] = 1;
	for(int i = 0; i < cur.size(); i++){
		build[cur[i]] = 1;
		if(i == 0) h[cur[i]] = t[from];
		else h[cur[i]] = t[cur[i - 1]];
		if(i == cur.size() - 1 && build[to]) t[cur[i]] = h[to];
		else t[cur[i]] = ++total;
	}
	if(!build[to]) 
		h[to] = t[cur.back()], t[to] = ++total, build[to] = 1;
	cur.clear();
}

int vis[N], in[N], out[N];
void dfs(int u){
	if(u != from) cur.push_back(u);
	vis[u] = 1;
	for(auto &v : G[u]){		
		if(vis[v] || out[v] == 0) to = v, insert();
		else dfs(v);
		from = u;
	}
}

int n;
bitset<N> con[N];

// con[u][v] 表示存在一条 v -> u 的路径

void topo(){
	queue<int> q;
	for(int i = 1; i <= n; i++)
		if(in[i] == 0) q.push(i);
	while(q.size()){
		int u = q.front(); q.pop();
		for(auto &v : G2[u]){
			if(--in[v] == 0) q.push(v);
			con[v] |= con[u]; con[v][u] = 1;
		}
	}
}
vector<int> rec[N];
int main(){
	ios::sync_with_stdio(false); 
	cin.tie(nullptr); cout.tie(nullptr);

	int m; cin >> n >> m;
	vector<pair<int, int>> edge;
	int u, v;
	for(int i = 0; i < m; i++){
		cin >> u >> v;
		edge.emplace_back(u, v); G2[u].push_back(v);
		in[v]++;
		// in[v]++, out[u]++, G[u].push_back(v);
	}
	topo();

	for(int i = 0; i < m; i++){
		auto [u, v] = edge[i]; int ok = 1;
		for(auto &p : G2[u])
			if(con[v][p]) {ok = 0; break;} 
		if(ok){
			G[u].push_back(v); in[v]++, out[u]++;
			// cout << u << " -> " << v << "\n";
		}
	}

	for(int i = 1; i <= n; i++){
		if(in[i] == 0 && out[i] == 0){
			h[i] = ++total, t[i] = ++total;
			continue;
		}
		if(in[i] == 0) from = i, dfs(i);
	}
	if(res == -1) return cout << -1, 0;

	assert(total <= 2 * n);
	cout << total << "\n";
	for(int i = 1; i <= n; i++)
		cout << h[i] << " " << t[i] << " " << i << "\n";
}