#include <fstream>
#include <vector>
#include <stack>
#include <algorithm>
#include <iostream>
using namespace std;

constexpr int my_negate(const int x, const int n){
	return (x < n) ? x+n : x-n; }

constexpr int undecided = 2, fa = 0, tr = 1;

class managed_stack{
	stack<int> st;
	vector<bool> v;
	void cl(){
		while(!st.empty() && !v[st.top()]){
			st.pop(); } }
public:
	managed_stack(const int n): v(n, false){}
	int top(){
		cl();
		return st.top(); }
	void push(const int x){
		st.push(x);
		v[x] = true; }
	void pop(){
		v[st.top()] = false;
		st.pop(); }
	void remove(const int x){
		v[x] = false; }
	bool check(const int x){
		return v[x]; } };
		
void dfs1(const vector<vector<int> >& v, const int cur, managed_stack& st,
	vector<bool>& e_folosit){
	for(const auto next : v[cur]){
		if(!e_folosit[next]){
			e_folosit[next] = true;
			dfs1(v, next, st, e_folosit); } }
	st.push(cur); }

void dfs2(const vector<vector<int> >& v, const int cur, managed_stack& st,
	vector<int>& componenta, vector<int>& which_comp, const int comp_cur){
	componenta.push_back(cur);
	which_comp[cur] = comp_cur;
	st.remove(cur);
	for(const auto next : v[cur]){
		if(st.check(next)){
			dfs2(v, next, st, componenta, which_comp, comp_cur); } } }

void do_print(const int x, const int n){
	if(x < n){
		cout << x+1; }
	else{
		cout << '!' << x-n+1; } }

class graf{
	vector<vector<int> > v;
	vector<vector<int> > tr;
public:
	void print(const int n){
		cout << v.size() << '\n';
		for(int i = 0; i < v.size(); ++i){
			do_print(i, n);
			cout << " -> ";
			for(const auto next : v[i]){
				do_print(next, n);
				cout << ' '; }
			cout << endl; } }
	graf(const int sz):
		v(sz), tr(sz){}
	int size(){
		return v.size(); }
	void resize(const int nsz){
		v.resize(nsz);
		tr.resize(nsz); }
	void add(const int a, const int b){
		v[a].push_back(b);
		tr[b].push_back(a); }
	void fix(){
		for(auto& x : v){
			sort(begin(x), end(x));
			x.erase(unique(begin(x), end(x)), end(x)); }
		for(auto& x : tr){
			sort(begin(x), end(x));
			x.erase(unique(begin(x), end(x)), end(x)); } }
	void mk_condensation(vector<vector<int> >& componente,
		vector<int>& which_comp,
		graf& cond){
		managed_stack st(v.size());
		{
			vector<bool> e_folosit(v.size(), false);
			for(int i = 0; i < v.size(); ++i){
				if(!e_folosit[i]){
					e_folosit[i] = true;
					dfs1(v, i, st, e_folosit); } } }
		for(int i = 0; i < v.size(); ++i){
			if(st.check(i)){
				const int comp_cur = componente.size();
				componente.push_back({});
				dfs2(tr, i, st, componente.back(), which_comp, comp_cur); } }
		cond.resize(componente.size());
		for(int i = 0; i < componente.size(); ++i){
			for(const auto cur : componente[i]){
				for(const auto next : v[cur]){
					if(i != which_comp[next]){
						cond.add(i, which_comp[next]); } } } }
		cond.fix(); }

		void toposort(vector<int>& ordine){
			ordine.reserve(v.size());
			vector<int> in_deg(v.size());
			for(const auto& y : v){
				for(const auto x : y){
					++in_deg[x]; } }
			stack<int> de_viz;
			for(int i = 0; i < v.size(); ++i){
				if(in_deg[i] == 0){
					de_viz.push(i); } }
			while(!de_viz.empty()){
				const int cur = de_viz.top();
				de_viz.pop();
				ordine.push_back(cur);
				for(const auto next : v[cur]){
					--in_deg[next];
					if(in_deg[next] == 0){
						de_viz.push(next); } } } }

	const vector<int>& get_adiac(const int x)const{
		return v[x]; } };

int main(){
	ifstream f("party.in");
	int n, m;
	f >> n >> m;
	const int graf_sz = 2*n;
	graf g(graf_sz);

	for(int i = 0, a, b, t; i < m; ++i){
		f >> a >> b >> t;
		--a, --b;
		switch(t){
		case 0:
			g.add(my_negate(a, n), b);
			g.add(my_negate(b, n), a);
			break;
		case 1:
			g.add(my_negate(a, n), my_negate(b, n));
			g.add(b, a);
			break;
		case 2:
			g.add(my_negate(b, n), my_negate(a, n));
			g.add(a, b);
			break;
		case 3:
			g.add(a, my_negate(b, n));
			g.add(b, my_negate(a, n));
			break; } }
	//g.print(n);

	vector<vector<int> > componente;
	vector<int> which_comp(2*n);
	graf cond(0);
	g.mk_condensation(componente, which_comp, cond);
	vector<int> topo;
	cond.toposort(topo);
	reverse(begin(topo), end(topo));
	vector<int> e_invitat(g.size(), undecided);
	for(const auto comp : topo){
		if(e_invitat[componente[comp].front()] == undecided){
			for(const auto x : componente[comp]){
				do_print(x, n);
				e_invitat[x] = tr;
				e_invitat[my_negate(x, n)] = fa; } } }
	{
		ofstream g("party.out");
		g << count(begin(e_invitat), begin(e_invitat)+n, tr) << '\n';
		for(int i = 0; i < n; ++i){
			if(e_invitat[i]){
				g << i+1 << '\n'; } } }
	return 0; }