wa on test 2:

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

const int N = 1e6+10;
int n,s,ed;
int pre[N],nextt[N],a[N],vis[N];

int main()
{
	scanf("%d %d",&s,&n);
	int p,k,nex;
	for(int i = 1;i <= n; ++i) {
		scanf("%d %d %d",&p,&k,&nex);
		nextt[p] = nex;
		a[p] = k;
		vis[abs(k)]++;
		if(nex != -1)
			pre[nex] = p;
		else ed = p;
	}
	p = ed;
	vector<int> loser;
	while(p != -1) {
		if(vis[abs(a[p])] > 1) {
			loser.push_back(p);
			nextt[pre[p]] = nextt[p];
			pre[nextt[p]] = pre[p];
			vis[abs(a[p])]--;
		}
		p = pre[p];
	}
	p = s;
	for(;p != -1; p = nextt[p]) {
		printf("%05d %d ",p,a[p]);
		if(nextt[p] == -1) printf("-1\n");
		else printf("%05d\n",nextt[p]);
	}
	int l = loser.size();
	for(int i = l-1;i > 0; --i) {
		p = loser[i];
		int np = loser[i-1];
		printf("%05d %d %05d\n",p,a[p],np);
	}
	if(l)
		printf("%05d %d -1\n",loser[0],a[loser[0]]);
	
	return 0;
}

AC:

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

const int N = 1e6+10;
int n,s,ed;
int pre[N],nextt[N],a[N];
bool vis[N];

map<int,int> mark;

int main()
{
	vector<pair<int,int>> win,loser;
	scanf("%d %d",&s,&n);
	int p,k,nex;
	for(int i = 1;i <= n; ++i) {
		scanf("%d %d %d",&p,&k,&nex);
		mark[p] = nex;
		a[p] = k;
	}
	p = s;
	while(p != -1) {
		if(vis[abs(a[p])]) loser.push_back({p,mark[p]});
		else win.push_back({p,mark[p]});
		vis[abs(a[p])] = true;
		p = mark[p];
	}
	for(int i = 0,l = win.size();i < l; ++i) {
		p = win[i].first;
		int np;
		if(i < l) np = win[i + 1].first;
		if(i == l - 1) printf("%05d %d -1\n",p,a[p]);
		else printf("%05d %d %05d\n",p,a[p],np);
	}
	
	for(int i = 0,l = loser.size();i < l; ++i) {
		p = loser[i].first;
		int np;
		if(i < l) np = loser[i + 1].first;
		if(i == l - 1) printf("%05d %d -1\n",p,a[p]);
		else printf("%05d %d %05d\n",p,a[p],np);
	}
	
	return 0;
}