本問題を解くには、\(3\) つ組 \((a_i, b_i, d_i)\) を \(i = 1, 2, \ldots, Q\) の順に見て問題文中の操作を実際にシミュレーションする過程で、各 \(3\) つ組を処理する際に下記の \(2\) 種類の操作が高速に行えれば良いです。

• 操作 A：今までに課された制約から、\(X_{a_i}- X_{b_i}\) の値が一意に限定されるかを判定し、限定されるならその値は何かを求める。
• 操作 B：\(X_{a_i} - X_{b_i} = d_i\) という制約を新たに課す。

以下、操作 A や操作 B を行うクエリを高速に処理するという問題を考えます。 ただし、矛盾が生じる（すべての制約を同時に満たす数列 \(X\) が存在しなくなる）ような制約の組み合わせは課さないものとします。 結論を述べると、これは以下で簡単に導入する 重み付き Union-Find などと呼ばれるデータ構造によって実現可能です。

まず、操作 A を下記のより簡単な操作 A’ に置き換えた場合、つまり、操作 A’ と操作 B を行うクエリを高速に処理する問題を考えてみます。

• 操作 A’：今までに課された制約から、\(X_{a_i}- X_{b_i}\) の値が一意に限定されるかを判定する（具体的にどの値に限定されるかを求める必要はない）。

これは通常のUnion-Find を用いて可能です。 具体的には、数列 \(X\) の \(N\) 個の要素 \(X_1, X_2, \ldots, X_N\) に対応する \(N\) 個の頂点 \(1, 2, \ldots, N\) を管理する Union-Find を用いて、 操作 B のたびに頂点 \(a_i, b_i\) を辺で結び、 操作 A’ では頂点 \(a_i, b_i\) が同じ連結成分に属するかどうかを判定すれば良いです。

これを操作 A を行えるように改良するには、上で用いた通常の Union-Find に、下記で定める長さ \(N\) の数列 \(W = (W_1, W_2, \ldots, W_N)\) の情報を持たせて管理すれば良いです。

\(W_v \coloneqq \) （ Union-Find 上での 頂点 \(v\) の親頂点を \(p\) とするときの、\(X_p - X_v\) として一意に限定される値）

ただし、\(v\) の親頂点が存在しない場合は \(W_v \coloneqq 0\) とする。

例えば、操作 A の処理で UnionFind 上で頂点 \(a_i, b_i\) が同じ連結成分に属する場合、\(X_{a_i} - X_{b_i}\) として一意に限定される値を求めるには、 UnionFind 上で頂点 \(a_i, b_i\) それぞれから、それらが属する有向木の根 \(r\) へのパス \(a_i = u_1 \rightarrow u_2 \rightarrow \cdots \rightarrow u_x = r\) と \(b_i = v_1 \rightarrow v_2 \rightarrow \cdots \rightarrow v_y = r\) をたどり、

\[ (W_{v_1} + W_{v_2} + \cdots + W_{v_{y-1}}) - (W_{u_1} + W_{u_2} + \cdots + W_{u_{x-1}}) \]

を求めれば良いです。（UnionFind の管理において union by rank や パス圧縮等を適切に行えば、たどるべきパスの長さは十分短く、計算時間は十分高速です。）

通常の Union-Find に上記の \(W\) の情報を加え、Union-Find自体の更新に対応して \(W\) も随時変更するようにしたものが、重み付き Union-Find などと呼ばれています。

以下に、C++ 言語による本問題の正解例を記載します。

#include <iostream>
typedef long long ll;
using namespace std;

ll n, Q;
ll parent[200001], weight[200001];

int root(int i){
	if(parent[i] == i) return i;
	int r = root(parent[i]);
	weight[i] = weight[parent[i]] + weight[i];
	return parent[i] = r;
}
bool unite(int i, int j, ll x){
	int root_i = root(i), root_j = root(j);
	if(root_i == root_j) return weight[j]-weight[i] == x;
	parent[root_i] = root_j;
	weight[root_i] = weight[j]-weight[i]-x;
	return true;
}

int main(void)
{
	cin >> n >> Q;
	for(int i = 1; i <= n; i++) parent[i] = i, weight[i] = 0;
	
	ll a, b, d;
	for(int i = 1; i <= Q; i++){
		cin >> a >> b >> d;
		if(unite(a, b, d)) cout << i << " ";
	}
	cout << endl;

	return 0;
}